84. 柱状图中最大的矩形

https://leetcode-cn.com/problems/largest-rectangle-in-histogram/

解法一：贪心

遍历heights数组，每次将下标i入栈，遇到比栈顶高度小的元素就开始处理栈，利用现有的最大元素计算最大面积，以i为右边界，栈顶为左边界，宽度用i - 1 - sidx计算 一直弹栈直到栈顶小于i处，可以理解为从高到低试探 数组最后加一个辅助的0，用作哨兵

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        largest = 0
        stack = []
        heights.append(0)
        for i in range(len(heights)):
            while len(stack) > 0 and heights[stack[-1]] >= heights[i]:
                h = heights[stack.pop()]
                sidx = stack[-1] if len(stack) > 0 else -1    #矩形左边界
                largest = max(largest, h * (i-sidx-1))
            stack.append(i)
        return largest