Python 中直方图中的最大矩形
pythonserver side programmingprogramming
假设我们有一个整数数组，表示直方图的高度。每个条形都有单位宽度。我们必须找到面积最大的矩形，如下所示 −
为了解决这个问题，我们将遵循以下步骤 −
创建堆栈，设置 i := 0，ans := 0
while i <高度的大小，然后
如果堆栈有 0 个元素或堆栈顶部元素的高度 <= height[i]，则
将 i 插入堆栈，将 i 增加 1
否则 −
x := 堆栈顶部元素，从堆栈中删除。
height := heights[x]
当堆栈不为空时，temp := height * (i * stack[-1] – 1)，否则 temp := height * i
ans := ans 和 temp 的最大值
当堆栈不为空时−
x := 堆栈顶部元素
height := height[x]，从堆栈中删除
temp := height * length of heights – 堆栈顶部元素 – 堆栈不为空时为 1，否则 temp := length of heights
ans := ans 和 temp 的最大值
返回 ans
示例
让我们看下面的实现，以便更好地理解 −
class Solution(object): def largestRectangleArea(self, heights): stack = [] i = 0 ans = 0 while i < len(heights): if len(stack) == 0 or heights[stack[-1]]<=heights[i]: stack.append(i) i+=1 else: x = stack[-1] stack.pop() height = heights[x] temp = height * (i-stack[-1]-1) if len(stack)!= 0 else height * i ans = max(ans,temp) while len(stack)>0: x = stack[-1] height = heights[x] stack.pop() temp = height * (len(heights)-stack[-1]-1) if len(stack)!= 0 else height* len(heights) ans = max(ans,temp) return ans ob = Solution() print(ob.largestRectangleArea([2,1,5,7,3,2]))
输入
[2,1,5,7,3,2]
输出
12
