> For the complete documentation index, see [llms.txt](https://kerasnoone.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kerasnoone.gitbook.io/garnet/suan-fa/zhan/84-zhu-zhuang-tu-zhong-zui-da-de-ju-xing.md).

# \[84]\[困难]\[栈] 柱状图中最大的矩形

## 题目描述

[84. 柱状图中最大的矩形](https://leetcode-cn.com/problems/largest-rectangle-in-histogram/)

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

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

![](https://1942165044-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI7KRyeBH5dlW-CkUtn%2Fsync%2F43600013ccd6021f95ca03d73190c5f17e0f42d7.png?generation=1616833244286779\&alt=media)

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

![](https://1942165044-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI7KRyeBH5dlW-CkUtn%2Fsync%2F7a1a0ca9d778e17c03d5d699d00a3424939c2c6a.png?generation=1616833244516276\&alt=media)

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

示例:

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

## 解题思路

### 暴力枚举

理解本题单调栈的做法, 需要先从暴力思路开始. **枚举以每个柱形为高度的最大矩形的面积**. 具体来说, 遍历每个柱, 对于每一个的高度向左右两边扩散, 求出以当前高度为矩形的最大宽度多少.

这样的方法时间复杂度是$$O(n^2)$$.

### 单调栈

是不是可以一次遍历, 不需要对每个柱进行中心扩散, 就能够计算出每一个高度所对应的那个最大面积矩形的面积呢?

因此需要以空间换时间, 这里需要使用的数据结构就是单调栈.

以数组`[2, 1, 5, 6, 2, 3]`为例.

* 对于第一个高度为2的柱子, 此时以它的高度对应的最大面积还不确定, 因为我们知道了它的左边界, 但右边界还没有确定. 将其加入栈中

  ![](https://1942165044-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI7KRyeBH5dlW-CkUtn%2Fsync%2Fac841423a0900c025fdea002dc458b9a5806d62e.png?generation=1616833246422748\&alt=media)
* 然后看到了高度为1的柱子, 它对应高度的最大面积肯定也是不确定的. 但它之前高度为2的柱子对应的最大面积已经可以确定了, 因为1限制了它的右边界

  ![](https://1942165044-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI7KRyeBH5dlW-CkUtn%2Fsync%2F2d90650264924675aadc1d211e4f3bbc96ac72e9.png?generation=1616833247388022\&alt=media)

  计算高度为2柱子对应的最大面积. 它的高度为2, 与阻碍它向右延伸的高度为1的柱子间隔为`1-0=1`, 因此对应的最大面积为2. 在一个柱子的最大面积确定后, 就可以从栈中弹出了, 对之后的计算不产生影响, 原因后面会体现.

  ![](https://1942165044-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI7KRyeBH5dlW-CkUtn%2Fsync%2F7fa0d1e9859455c4f1dc3cf6c248410dbf119309.png?generation=1616833246290207\&alt=media)

  将新的为确定最大面积的高度为1的柱子压入栈.
* 遇到高度为5的柱子, 同样对应的最大面积为止. 这时再看下栈中的高度为1的柱子, 5的出现并没有影响它向右扩展, 因此它的最大面积也还不能确定. 将高度为5的柱子压入栈中

  ![](https://1942165044-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI7KRyeBH5dlW-CkUtn%2Fsync%2F7ea3ca99a212fc775d95fb179a689c4fbb61d149.png?generation=1616833245674234\&alt=media)
* 同样对于高度为6的柱子, 它自身, 以及栈中的高度为1, 5的柱子都没有确定右边界, 不能出栈. 将高度为6的柱子压入栈中

  ![](https://1942165044-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI7KRyeBH5dlW-CkUtn%2Fsync%2F7b5763227b17bfa98668952888f4aae6c937a3b1.png?generation=1616833247593783\&alt=media)
* 遇到高度为2的柱子, 它本身的最大面积肯定是还没有确定的. 但栈顶高度为6的柱子的最大面积可以确定了, 它的左侧被新的高度为2的柱子卡住, 右侧被高度为5的柱子卡住, 因此对应的最大面积为6, 这是因为它左右两侧柱子围住的宽度为`6-4-1=1`

  ![](https://1942165044-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI7KRyeBH5dlW-CkUtn%2Fsync%2Fa4ec1155cd803fc90264215881673bf13c38642d.png?generation=1616833245858994\&alt=media) ![](https://1942165044-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI7KRyeBH5dlW-CkUtn%2Fsync%2Fc899b04ceb8592f08671459c536992d5c0f71bac.png?generation=1616833246901062\&alt=media)

  而且弹出6后, 此时的新栈顶, 高度为5的柱子的最大面积也确定了, 它的左侧被1位置的柱子卡住, 右侧被4位置卡住, 对应的宽度为`4-1-1=2`, 因此对应的高度为10.

  ![](https://1942165044-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI7KRyeBH5dlW-CkUtn%2Fsync%2Fdffebcbed56a5a9764c0413efd76ae5f871595e1.png?generation=1616833246220749\&alt=media) ![](https://1942165044-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI7KRyeBH5dlW-CkUtn%2Fsync%2F29fc734d807ea3312be83ae3945d22afc13b15c0.png?generation=1616833247157274\&alt=media)

  将其高度为5, 位置为2的柱子也弹出, 将位置4的柱子压入.
* 遇到最后一个柱子, 也无法判断对应的最大面积, 压入栈

**总结上面的步骤**:

* 遇到当前柱形的高度比它上一个柱形的高度严格小的时候, 说明栈中至少有栈顶一个柱子的右侧延伸到头了
  * 而这些柱子的左侧最近的一个比它矮的柱子一定还在栈中. 因为这个柱子进来的时候, 会将栈中比它高的柱子弹出
  * 这些更高的柱子可以被弹出并忽略, 因为他们已经不妨碍后面新柱子向左的扩展, 新柱子只需要找到向左穿过这些更高柱子后最近的一个矮柱子
  * 被弹出的柱子对应的最大面积已经确定了, 与全局变量比较并更新
  * 由于更高的柱子被弹出, 这个最近的更矮的柱子就是栈中的下一个元素(重复的情况之后讨论)
* 栈中除了记录柱子的高度, 还要记录柱子的位置, 这样才能计算宽度

此时的栈中还有还有3个柱子:

![](https://1942165044-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI7KRyeBH5dlW-CkUtn%2Fsync%2F74aaf9a30a7f39cc3735688341c1421464236453.png?generation=1616833246805128\&alt=media)

现在这三个柱子的高度也可以确定了, 因为他们的左右边界都已经确定了.

* 对于最后一个高度为3的柱子, 它的是数组的右侧边界, 而它的左侧边界就是栈中的下一个元素, 因此对应的宽度为`5-4=1`, 最大面积为3

  ![](https://1942165044-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI7KRyeBH5dlW-CkUtn%2Fsync%2F9e463c8e63d4244f5959017b36bd5a1dae2a187b.png?generation=1616833244985996\&alt=media) ![](https://1942165044-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI7KRyeBH5dlW-CkUtn%2Fsync%2F4aa28164e267743c701a2c287bf11d4fa4dea804.png?generation=1616833245341996\&alt=media)
* 位置4的柱子向右可以延伸到右侧边界, 向左可以延伸到栈中的下一个元素, 对应宽度为`5-1=4`, 因此对应的最大面积为8

  ![](https://1942165044-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI7KRyeBH5dlW-CkUtn%2Fsync%2Fc60a07dbb3351910aebff1effb1eb831e14e4583.png?generation=1616833245617914\&alt=media)
* 最后还剩一个高度为1的柱子, 它向右也可以延伸到右侧边界, 左侧可以延伸到栈的下一个元素. 但此时栈中只有它一个元素, 所以说明它可以向左延伸至左侧边界, 因此对应的宽度为整个数组的长度`6`, 对应的最大面积是6

  ![](https://1942165044-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI7KRyeBH5dlW-CkUtn%2Fsync%2F9ff1514aa7b30026d39c1b92e8965d136822c4cf.png?generation=1616833244726271\&alt=media) ![](https://1942165044-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI7KRyeBH5dlW-CkUtn%2Fsync%2Fbeb2c22d5ae3d6b37c303807d273efea484dfe84.png?generation=1616833245087057\&alt=media)

这一步可以总结如下:

* 最后还在栈中的柱子, 说明他们向右都可以扩展到右侧边界
* 他们的左侧边界跟之前一样, 也是各自所紧邻栈中的下一个元素

因此观察整个过程中更新栈的逻辑, 遇到更大值时直接压入栈, 遇到下一个较小值时, 将栈顶比这个值大的元素都弹出, 再将其入栈, 因此保持了一个**单调递增栈**的结构. 之所以使用单调栈的结构, 前面已经提及, 即**这些更高的柱子可以被弹出并忽略, 因为他们已经不妨碍后面新柱子向左的扩展, 新柱子只需要找到向左穿过这些更高柱子后最近的一个矮柱子**. 我们可以使用单调栈的性质, **快速找到左侧最近的更矮的柱子**. 而右侧的边界则可以在遍历过程中确定.

**重复元素**

还需要考虑的一个细节是, 在确定一个柱形的面积的时候, 除了**右边要比当前严格小**, **左边也要比当前高度严格小**. 如果遇到相同高度的柱子该怎么办?

在右边遍历的时候, 如果遍历到的当前柱子与栈顶柱子的高度相等, 那么栈顶柱子向右发展实际上没有受到阻碍, 因此无需弹出, 直接将新的柱子压入.

在弹出栈中元素时, 被弹出的柱子需要确定它左边的边界. 一般它的左侧边界就是紧邻的栈中下一个柱子, 但可能下一个柱子的高度与这个柱子相同, 那下一个柱子肯定不是左侧边界.

但其实在计算被弹出柱子的面积时, 它的右侧是确定的, 就是当前触发栈中元素弹出的位置. 因此栈中几个**相邻**的同样高度的柱子都会被弹出, 那么这些同样高度柱子最左侧的一个, 对应的面积是真正的这个高度对应的最大面积, 而最左侧的这个柱子的左侧边界就是它的下一个元素.

那么相同高度的其他几个柱子对应的面积也就不重要了, 可以不考虑, 因此可以保持找下一个元素的计算方式, 保持逻辑的一致性.

**哨兵**

可以看到上面的处理过程有两个特殊点:

* 最终栈中还是有元素, 需要再次遍历一遍栈
* 如果栈中只有一个元素, 这个元素出栈时, 相当于它的左侧边界为最左侧

因此可以在左右两侧各添加一个高度为0的哨兵(只要比最小高度1更小就可以). 有了这两个柱形哨兵:

* 左边的哨兵由于一定比输入数组里任何一个元素小, 它肯定不会出栈, 因此栈一定不会为空
* 右边的哨兵也正是因为一定比输入数组里任何一个元素小, 它会让所有输入数组里的元素出栈

对应的代码为:

```python
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        heights = [0] + heights + [0]  # 添加左右哨兵
        stack = [0]  # 左侧哨兵入栈
        max_area = 0

        for i in range(1, len(heights)):
            while heights[i] < heights[stack[-1]]:
                index = stack.pop()
                h = heights[index]
                max_area = max(max_area, (i - stack[-1] - 1) * h)
            stack.append(i)

        return max_area
```

## 参考资料

* [暴力解法、栈（单调栈、哨兵技巧）](https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/bao-li-jie-fa-zhan-by-liweiwei1419/)