此题一个比较好的思路是中心扩散法，即对每个柱子，找到以他为最小值的区间。这个状态比较难用dp优化，因为不确定区间中到底包含几个最小值。
另一个很好的O(N)思路就是单调栈，保持栈是一个递增序列，这样这个序列是共享同一个最小值的。当新的最小值出现，这个序列可以把之前比他大的元素排掉（此元素两端最长扩散长度已经出现）并记录他们的结果，留下序列长度让新的最小值用。如此往复即可完成操作。直接存其实是很难做的，因为要记录已经排出的柱子。最好的办法是把索引存进去，可以通过索引比较距离。

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        ret = 0
        stack = []
        heights = [0] + heights + [0]

        for i, h in enumerate(heights):
            while stack and h < heights[stack[-1]]:
                # 取值为这个和上个相减（距离）* 高度
                val = (i-stack[-2]-1)*heights[stack[-1]]
                if val > ret: ret = val
                stack.pop()

            stack.append(i)

        return ret

其中，这题很大的一个亮点是在前后加了两个0，前面的0可以保证能索引到倒数第二个元素，看与前面的差的索引，后面的0是保证把最后的给处理掉。