84. 柱状图中最大的矩形

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

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

_static/images/84.png

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

_static/images/84-2.png

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

示例:

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

小技巧

矩形面积要最大的话，需要尽可能的使得连续的矩形多，并且最低一块的高度要高。

我们需要按从高板子到低板子的顺序处理，先处理最高的板子，宽度为1，然后再处理旁边矮一些的板子，此时长度为2，因为 之前的高板子可以与矮板子的矩形 ，因此我们需要一个递增栈，当遇到大的数字直接进栈，而当遇到小于栈顶元素的数字时，就要取出栈顶元素进行处理了，那取出的顺序就是从高板子到矮板子了，于是乎遇到的较小的数字只是一个触发，表示现在需要开始计算矩形面积了

找两边第一个小于它的值 ，对于首位元素，我们通过添加 0 来创造其缺失的 两边元素 。【遇到的较小的数字只是一个触发】这个触发的数字其实就是栈顶元素的 右边界 即右边第一个小于栈顶元素的值，然后通过不算取出队列中的元素，直到遇到 左边界 即左边第一个小于栈顶元素的值

备注

  • 时间复杂度：O(n), n 个数字每个会被压栈弹栈各一次

  • 空间复杂度：O(n)

class Solution(object):
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        heights = [0] + heights + [0]
        area = 0
        stack = []
        for i in range(len(heights)):
            while stack and heights[stack[-1]] > heights[i]:
                tmp = stack.pop()
                area = max(area, heights[tmp] * (i - stack[-1] - 1))
            stack.append(i)
        return area