【Leetcode】84. 柱状图中最大的矩形

题目

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

1

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

2

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

示例:

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

题解

拿到这个问题很容易想到，对于每一个柱形图，只要向左向右去遍历，然后找到左边第一个小于他的点和右边第一个小于他的点，就可以得到宽度，然后再乘上它的高，就可以得到当前的矩形面积。从左到右依次遍历并且更新结果，最后就可以求得最大的矩形面积。

容易得到，这个解法的时间复杂度为O(n^2)，那么怎么优化呢，首先要考虑，从左到右的遍历是免不了的，那么对于每一个点，求解它左右的第一个小于它的元素，这个点是不是可以优化呢。所以这里就用到了单调栈，我们可以花费一点空间，用一个栈来维护一组下标，对于栈中的每一个下标所对应的元素，它的左边第一个比他小的元素的下标就是栈中的前一个下标，有了这样的思路，就容易解决问题了。

还是模拟一下过程，对于图中的测试样例。创建一个stack,然后进行遍历

• 第一个元素，直接入栈，栈中元素为0（2），栈中保存下标，括号里面表示对应的元素
• 第二个元素，比第一个元素小，弹出第一个元素，弹出第一个的元素的时候，要计算它左右能达到的面积，2对应的最大面积为2*1，更新面积，然后第二个元素入栈，栈中元素1（1）
• 第三个元素，入栈，栈中元素1（1）、2（5）
• 第四个元素，入栈，栈中元素1（1）、2（5）、3（6）
• 第五个元素，比栈顶的要小，所以要出栈，首先3出栈，6对应的左边第一个比他小的就是下标2对应的5，右边就是当前的下标对应的2，所以面积为6，然后5出栈，他左边第一个比他小的是下标1对应的1，右边则是当前下标对应的2，所以更新面积得到10。然后入栈，栈中元素1（1）、4（5）
• 最后一个元素3，入栈，栈中元素1（1）、2（5）、3（6），然后依次弹出，并更新面积。

这里在内部看起来有了一个出栈的循环，实际上，每个元素都只要一次入栈和出栈的机会，所以实际上这里进行了2*n次操作，所以时间复杂度就是O(n)。

python

class Solution:
    def largestRectangleArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if height == None:
            return 0
        stack = []
        #添加-1是为了判断是不是进行到了最后一个
        height.append(-1)
        ans = 0
        for i in range(len(height)):
            cur = height[i]
            #如果栈为空或者当前柱比栈顶柱要高，入栈
            if len(stack) == 0 or cur >= height[stack[-1]]:
                stack.append(i)
            else:
            #如果栈不为空并且当前柱比栈顶柱要低，出栈，更新结果。
                while len(stack) != 0 and cur <= height[stack[-1]]:
                    h = height[stack.pop()]
                    left = stack[-1] if len(stack)!=0 else -1
                    ans = max(ans,h*(i-left-1))
                stack.append(i)
        return ans