Python程序：查找直方图中最大矩形面积

假设我们有一列数字，表示直方图中条形的高度。我们需要找到可以在条形下形成的最大矩形的面积。

因此，如果输入类似于 nums = [3, 2, 5, 7]

则输出将为 10

为了解决这个问题，我们将遵循以下步骤：

  • stk := 一个栈，最初插入 -1 到其中
  • 在heights的末尾插入0
  • ans := 0
  • 对于 i 从 0 到 heights 的大小，执行：
    • 当 heights[i] < heights[栈顶] 时，执行：
      • h := heights[栈顶] 并从栈中弹出
      • w := i - 栈顶 - 1
      • ans := ans 和 (h * w) 的最大值
    • 将 i 推入栈中
  • 返回 ans

让我们看看下面的实现以更好地理解：

示例

在线演示

class Solution:
   def solve(self, heights):
      stk = [-1]
      heights.append(0)
      ans = 0
      for i in range(len(heights)):
         while heights[i] < heights[stk[-1]]:
            h = heights[stk.pop()]
            w = i - stk[-1] - 1
            ans = max(ans, h * w)
         stk.append(i)
      return ans

ob = Solution()
nums = [3, 2, 5, 7]
print(ob.solve(nums))

输入

[3, 2, 5, 7]

输出

10

更新于：2020年12月2日

1K+ 次浏览

启动你的职业生涯

通过完成课程获得认证

开始学习
广告