博客

解题思路： 单调栈 

先说单调栈，单调栈是一种特殊的栈，特殊的地方在于，每当有元素入栈时，只要栈顶元素大于要入栈的元素，栈顶元素就要弹出，直到栈顶元素小于等于当前元素，当前元素再入栈。所以说单调栈总是自底至顶单调的。

对于这道题来说，寻找最大面积的矩形，我们只要把每个元素作为高的最大矩形都求出来，再求最大即可。

遍历heights，大于栈顶元素则入栈。当栈顶元素大于当前元素，弹出栈顶，此时计算弹出栈顶元素为高的最大矩形面积，因为是单调栈，所以栈内的元素均小于当前元素，要进栈的元素又一定小于出栈元素。

所以，当栈不为空时：area = heights[x] * (i-stack[-1]-1)；栈空时：area = heights[x] * i

代码：

class Solution(object):
    def largestRectangleArea(self, heights):
        """单调栈"""
        heights.append(0)
        stack = [0]
        area = 0
        for i in range(1, len(heights)):
            if heights[i] >= heights[stack[-1]]: #大于栈顶元素则入栈
                stack.append(i)
            else:
                while stack and heights[i] < heights[stack[-1]]: #只要栈非空且栈顶元素大于当前元素
                    x = stack.pop(-1) #弹出栈顶 此时计算以该元素为高的最大矩形
                    if len(stack) != 0:
                        area = max(area, heights[x] * (i-stack[-1]-1))
                    else:
                        area = max(area, heights[x] * i)
                stack.append(i)
        return area