在Python中查找直方图下最大矩形面积的程序
假设我们有一个数字列表,代表直方图中条形的高度。我们必须找到可以在条形下形成的最大矩形的面积。
所以,如果输入是nums =[3,2,5,7]
然后输出将是10
为了解决这个问题,我们将遵循以下步骤−
- 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
- 当heights [i] < heights [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))
输入
[3,2,5,7]
输出
10