剑指 Offer II 039. 直方图最大矩形面积 单调栈

剑指 Offer II 039. 直方图最大矩形面积
该矩阵的宽度一定是，从栈顶柱子的两边出发直到遇到比该柱高矮的柱子所夹成的宽度。
因为单调栈中保存的柱高是递增的，所以栈中位于栈顶柱子前面的柱子一定比栈顶柱子矮，同样当前扫描到的柱子也矮于位于栈顶的柱子，所以顶柱子为顶的最高矩阵的宽度就确定了，那么面积也就确定了。

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        heights.append(0)   #最后一个柱形高度为0，列表剩下的元素全都会pop出计算其为高度时的最大矩形面积
        lenh=len(heights)
        maxArea=0
        h=[-1]
        for i in range (lenh):
            while h[-1]!=-1 and heights[i]<heights[h[-1]]:
                area_height=heights[h[-1]]
                h.pop()
                area_width=i-h[-1]-1     #只剩一个柱形元素时，左边界index可当作-1
                maxArea=max(maxArea,area_height*area_width)
            h.append(i)        #此时heights[i]>heights[h[-1]]
        return maxArea