在Python中查找直方图下最大矩形面积的程序

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

所以，如果输入是nums =[3,2,5,7]

然后输出将是10

在Python中查找直方图下最大矩形面积的程序

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

stk：一个堆栈，最初将其插入-1
在高度的结尾插入0
ans：0
对于i在0到高度大小的范围内，执行以下操作
- 当heights [i] < heights [stk的顶部]时，执行以下操作
  - h：heights [stk的顶部]并从stk中推出
  - w：i-stk[stk的顶部]-1
  - ans：ans和（h*w）的最大值
- 将i推入stk
返回ans

让我们看一下以下实现以获得更好的理解−

更多Python相关文章，请阅读：Python 教程

示例

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))