leetcode 084. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

image.png

`

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]

image.png

`

图中阴影部分为所能勾勒出的最大矩形面积，其面积为10;个单位。

示例:`

输入: [2,1,5,6,2,3]
输出: 10`

思路：
用一个单调递增的栈来放bar，如果是递增的就放进栈，那么当前bar的左边界就是前一个元素（比当前bar高度低的元素），循环数组的时候，遇到高度比栈顶bar高度低，说明找到了栈顶bar的右边界，高度就是栈顶bar高度，宽度就是右边界-左边界（数组当前位置到栈bar前一个位置的距离，即i-stack[-2]-1）。每找到一个小于栈顶高度的需要循环和栈内元素做判断并计算最大面积，计算完最大面积就弹出栈。height队尾放入0是为了方便计算宽度，同时0高度最低，会把栈内元素面积都计算完。stack放入-1是为了方便计算左边界。`

参考图如下，不完全相同

image.gif

`

class Solution:
    def largestRectangleArea(self, heights):
        # 在队尾加一个0方便计算宽度
        heights.append(0)  
        # 新增一个单调递增栈放矩形
        stack = [-1] 
        area = 0
        for i in range(len(heights)):
            # 如果当前bar的高度height[i]低于栈顶bar高度，说明栈顶bar找到右边界，且由于是单调递增栈，栈顶前一个bar为左边界stack[-2]，则可以计算当前高度最大面积
            while heights[i] < heights[stack[-1]]:
                # 高度为栈顶bar高度
                h = heights[stack[-1]]
                # 宽度为左右边界
                w = i - stack[-2] - 1
                area = max(area, h * w)
                # 计算完最大面积后就弹出栈
                stack.pop()
            # 如果当前bar的高度height[i]大于等于栈顶，说明栈顶bar还没找到右边界，继续放入栈
            stack.append(i)
        return area

su = Solution()
heights = [2, 1, 2]
res = su.largestRectangleArea(heights)
print(res)