LC 84柱状图中最大的矩形Largest Rectangle in Histogram　困难

给定柱状图中各柱的高度（每柱宽为 1），求在该图中能勾勒出的最大矩形面积。

思路 单调递增栈 + 首尾哨兵 0：某柱出栈时，其高度能延伸的宽度由新的栈顶决定，面积 h*(i-st[-1]-1) 取最大。O(n)。

class Solution:
    def largestRectangleArea(
            self, heights: List[int]) -> int:
        heights = [0] + heights + [0]
        st = [0]
        ans = 0
        for i in range(1, len(heights)):
            while heights[st[-1]] > heights[i]:
                h = heights[st.pop()]
                w = i - st[-1] - 1
                ans = max(ans, h * w)
            st.append(i)
        return ans