给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

示例:
输入: [2,1,5,6,2,3]
输出: 10

思路

1. 暴力枚举。
   两个柱子间矩形的高由他们之间最矮的柱子决定。在枚举矩形的时候，首先是枚举底长[i:j+1]，然后在底长范围中找到最低高度min(heights[i:j+1])，底长和最低高度相乘计算面积。
   时间复杂度O(n**3)，空间复杂度O(1)。

    def largestRectangleArea(self, heights: List[int]) -> int:
        if len(heights)== 0:
            return 0
        if len(heights) == 1:
            return heights[0]
        max_area = 0
        for i in range(len(heights)):
            for j in range(i, len(heights)):
                sub = heights[i:j+1]
                area = (j-i+1) * min(sub)
                max_area = max(max_area, area)
        return max_area

2. 分治法。
   以最小高度为中心，将区域分为3份，区间的最大面积为
   max（
   最小高度 * 区间长度，
   最小高度左边最大面积，
   最小高度右边最大面积
   ）

    def largestRectangleArea(self, heights: List[int]) -> int:
        def devide(left, right):
            if right < left:
                return 0
            min_index = left
            for i in range(left, right + 1):
                if heights[i] < heights[min_index]:
                    min_index = i
            return max((right-left+1)*heights[min_index], devide(left, min_index-1), devide(min_index+1, right))
        if len(heights) == 0:
            return 0
        if len(heights) == 1:
            return heights[0]
        return devide(0, len(heights)-1)

以上两种方法，使用python均超时

3. 栈
   维护一个栈，初始化将 -1入栈。
   遍历heights数组，如果heights[i] > heights[i-1]，即heights[i]大于栈顶元素，则下标i入栈；
   如果heights[i]<heights[i-1]，开始将栈顶元素弹出，直到遇到栈顶元素小于heights[i];
   每次弹出下标计算的面积为：
   （栈顶元素的左边界永远是栈内它的下一个元素， 右边界是遇到的比它小的第一个元素）
   以栈顶元素为高 * 右边界到左边界之间的矩形为宽
   即： heights[stack[top]] x (i - stack[top - 1] -1)
   当达到数组尾部时，将栈中剩余元素全部弹出栈，在弹出时计算面积的公式为：
   heights[stack[top]] x (heights.length - stack[top-1] - 1)

def largestRectangleArea(self, heights: List[int]) -> int:
        if len(heights) == 0:
            return 0
        if len(heights) == 1:
            return heights[0]
        stack = [-1]
        max_area = 0
        for i in range(len(heights)):
            while stack[-1] != -1 and heights[i] < heights[stack[-1]]:
                h = stack.pop()
                area = heights[h] * (i - stack[-1] - 1)
                max_area = max(max_area, area)
            stack.append(i)
        while stack[-1] != -1:
            h = stack.pop()
            area = heights[h] * (len(heights) - stack[-1] - 1)
            max_area = max(max_area, area)
        return max_area