84. 柱状图中最大的矩形

https://blog.csdn.net/qq_23262411/article/details/103593476  和这个题有点像。

对于单调的排列情况是最简单的，以每一个位置为起点找形成的最大矩形，因为排列是单调的，所以后面的要比这个位置高，也就是该位置是最低的一个位置，这个位置的高度也就是这个矩形的高度。最大矩形的长度就应该是从这个位置到单调排列末尾的距离。

在一个单调的排列里就可以通过这种方法找出所有可能的矩形，从中选出最大的。

 

但是普遍的排列不是整体的单调的，不过由于现在这个最高的位置他的高度不能和别的位置组成矩形，所以可以忽略这个最高的位置，它后面这个位置仍然可以和前面的组成单调排列。

从目前的位置，直接可以略过比它高的位置。

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack = []
        # 前面添加0 是为了栈不为空保证能计算面积
        heights = [0] + heights + [0]
        res = 0
        # 在heights的末尾添加0 是为了完整的更新面积
        for i in range(len(heights)):
            # 只要出现降序  就更新面积
            while stack and heights[stack[-1]] > heights[i]:
                tmp = stack.pop()
                res = max(res, (i - stack[-1] - 1) * heights[tmp])
            stack.append(i)
        return res