【LeetCode】84. 柱状图中最大的矩形（单调栈）

1. 题目描述

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

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

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

示例:

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

2. 解题思路

其实可以把这个想象成锯木板，如果木板都是递增的那我很开心，如果突然遇到一块木板 $i$ 矮了一截，那我就先找之前最戳出来的一块（其实就是第 $i - 1$ 块），计算一下这个木板单独的面积，然后把它锯成次高的，这是因为我之后的计算都再也用不着这块木板本身的高度了。再然后如果发觉次高的仍然比现在这个 $i$ 木板高，那我继续单独计算这个次高木板的面积（应该是第 $i - 1$ 和 $i - 2$ 块），再把它俩锯短。直到发觉不需要锯就比第 $i$ 块矮了，那我继续开开心心往右找更高的。当然为了避免到了最后一直都是递增的，所以可以在最后加一块高度为 $0$ 的木板。

这个算法的关键点是把那些戳出来的木板早点单独拎出来计算，然后就用不着这个值了。

参考：LeetCode讨论区.

2.1 暴力法

首先，要想找到第 $i$ 位置最大面积（以第 $i$ 根柱子为最矮柱子所能延伸的最大面积）是什么？

是以 $i$ 为中心，向左找第一个小于 $h e i g h t s [i]$ 的位置 $left_i$ ；向右找第一个小于于 $h e i g h t s [i]$ 的位置 $right_i$ ，即最大面积为 $heights[i] * (right_i - left_i -1)$ ，如下图所示：
所以，我们的问题就变成如何找 $right_i$ 和 $left_i$
最简单的思路就是，就是暴力法，直接分别在 $i$ 左右移动。

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        res = 0
        for i in range(n):
            l = i
            r = i
            while l >= 0 and heights[l] >= heights[i]:
                l = l - 1
            while r < n and heights[r] >= heights[i]:
                r = r + 1
            res = max(res, heights[i] * (r - l - 1))
        return res

但是，这是一个时间复杂度为 $O(n^2)$ ，超时。
接下来想办法优化。

2.2 单调栈（空间换时间）

具体可以参考 LeetCode官方题解（视频动画）.

所谓单调栈，本质上还是栈，即满足先进后出的原则，在Python 中实现可以用 List 实现。所谓单调，即单调递增或者单调递减。

单调递增栈可以找到左边第一个比当前出栈元素小（含等于）的元素
单调递减栈可以找到左边第一个比当前出栈元素大（含等于）的元素

具体解题步骤：

本题中，当看到柱子递增时，将下标入栈，（栈中只存下标，因为高度可以直接通过下标访问）；
当柱子下降时，将栈顶元素 stack[-1] pop 出来，并且计算当前的面积 $h e i g h t [i] * (i - s t a c k [- 1] - 1)$ ，注意这里要用弹出一个栈顶后的新栈顶 stack[-1]，具体可看下面代码

技巧：这里在最前面和最后面分别加了一个“哨兵”，目的是避免了特殊处理。

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        heights = [0] + heights + [0]
        n = len(heights)
        stack = []   # 只存下标，因为高度可以直接通过下标访问
        res = 0
        for i in range(n):
            while stack and heights[stack[-1]] > heights[i]:   # 判断栈顶元素是否比较大，即开始下降，需要出栈了
                top = stack.pop()    # 先出栈，栈顶元素就是前面低一点的那个
                res = max(res, heights[top] * (i - stack[-1] - 1)) # 这里不能用 i-top-1 因为top已经被弹出了
            stack.append(i)     # 如果柱子不断上升，则入栈
        return res

参考：

LeetCode题解.