如何枚举出所有情况

枚举所有柱形的上边界作为整个矩形的上边界
然后求出左右边界：
1、找出左边离它最近的，比它小的柱形
2、找出右边离它最近的，比它小的柱形

单调栈

stk:存储左边离当前柱子最近的比它小的柱形，及该柱形右边所有的柱形的索引
如 柱子高度序列为 2，1，5，6，2，3
当遍历第二个2时，stk初始为2，1，5，6
此时1左边的2可以删去，因为2比1大，且在1左边，所以如果给定数比2要大，那么肯定比1大
所以只要1在2右边，就不会取得到2
当把所有类似上述2的冗余删除后，必然得到一个单调栈
得到单调上升的栈

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        left = [0 for i in range(n)]; right = [0 for i in range(n)]
        stk = [] # 存储柱形的索引
        # 找左边界
        i= 0
        while i < n: # 从左到右遍历
            while len(stk) > 0 and heights[stk[-1]] >= heights[i]:
                stk.pop()
            if not len(stk): left[i] = -1 
            # 假设柱形图左右边界都是负无穷
            # 若左边没有比它小的柱形，则整个柱形图的左边界就是它的左边界，索引为-1
            else: 
                left[i] = stk[-1] # 若存在，则为栈顶元素
            stk.append(i) # stk存储当前柱形的索引   
            i += 1

        while len(stk) > 0: stk.pop() # 先清空单调栈
        # 找右边界
        i = n - 1
        while i >= 0: # 从右到左遍历
            while len(stk) > 0 and heights[stk[-1]] >= heights[i]:
                stk.pop()
            if not len(stk): right[i] = n  
            # 假设柱形图左右边界都是负无穷
            # 若右边没有比它小的柱形，则整个柱形图的右边界就是它的左边界，索引为n
            else: 
                right[i] = stk[-1] # 若存在，则为栈顶元素
            stk.append(i) 
            i -= 1

        res = 0
        for i in range(n):
            res = max(res, heights[i] * (right[i] - left[i] - 1))
            # 右边界减去左边界再减去一才是中间部分的宽度（柱子的个数）
        return res