084.柱状图中最大的矩形
作者：沉默王二
发布时间：2023-09-30T20:36:47.459+0800
本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记），访问地址和密码：https://t.zsxq.com/6iuzn6I
题意
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
难度
困难
示例
示例1：
输入：heights = [2,1,5,6,2,3]
解释：最大的矩形为图中红色区域，面积为 10
示例2：
输入： heights = [2,4]
分析
这题看上去很难，也确实是一道困难题，但实际上我们可以通过几条定理的逐步证明，来将它拆分成一道简单题。
我们先把柱子的高度和矩形的“高度”都称为l，把矩形的“宽度”，也就是矩形在x轴上的距离，称为r。
定理1：面积最大的矩形的高度l，必然和一个柱子的高度l相等。
证明：
这个问题的关键在于，当我们选择一个柱子的高度 ( h ) 作为矩形的高度时，我们总是希望该矩形尽可能地在左右两边扩展，以获得最大的面积。
我们来反证法来证明这个结论：
假设存在一个矩形，其面积是最大的，高度为 ( h )，但是在柱状图中没有任何一个柱子的高度正好为 ( h )。那么这个矩形的高度 ( h ) 是怎么来的呢？
- 由于矩形的高度 ( h ) 必然是由两个柱子（或多个）的最小值决定的。设这两个柱子的高度分别为 ( h1 ) 和 ( h2 ) （其中 ( h1 \geq h ) 和 ( h2 \geq h )），它们之间可能还有其他高度的柱子。但由于这个矩形的高度为 ( h )，我们可以知道 ( h1 ) 和 ( h2 ) 之间的所有柱子的高度都不小于 ( h )。
- 如果 ( h1 ) 或 ( h2 ) 中的任何一个高度大于 ( h )，那么我们完全可以选择高度 ( h1 ) 或 ( h2 ) 中的较小者作为矩形的高度，并保持矩形的宽度不变，这样得到的矩形面积肯定会比高度为 ( h ) 的矩形面积更大。这与假设矛盾，因为我们假设了高度为 ( h ) 的矩形面积是最大的。
由此，我们可以得出结论：面积最大的矩形的高度必然和柱状图中的某个柱子的高度相等。
定理2：每个柱子能扩展的最大矩形面积的“宽度”，取决于它左边和右边延伸出去的第一个比它小的柱子。
证明：
这个观点可以通过反证法来解释：
假设我们有柱子 A，其高度为 h。为了确定柱子 A 能够扩展的最大矩形面积的“宽度”，我们要在它的左边和右边查找第一个高度小于 h 的柱子。
- 左边：假设柱子 A 的左边有一个柱子 B，它的高度也是 h 或更高，那么以 A 为高度的矩形可以向左扩展到 B，因为 B 的高度不会限制 A 所形成的矩形的高度。但如果 B 的左边是一个比 h 低的柱子 C，那么 C 就会限制以 A 为高度的矩形向左的扩展。所以，我们可以说 A 能够扩展的最大矩形的“宽度”（在左边）取决于它左边的第一个比它小的柱子 C。
- 右边：类似地，如果柱子 A 的右边有一个柱子 D，其高度也是 h 或更高，那么以 A 为高度的矩形可以向右扩展到 D。但如果 D 的右边是一个比 h 低的柱子 E，那么 E 会限制以 A 为高度的矩形向右的扩展。因此，A 能够扩展的最大矩形的“宽度”（在右边）取决于它右边的第一个比它小的柱子 E。
反证：假设 A 能够扩展的最大矩形的宽度不取决于它左边和右边的第一个比它小的柱子。那么这意味着我们可以继续向左/右扩展该矩形而不受任何限制，直到遇到另一个高度为 h 或更高的柱子，但这与我们的假设矛盾，因为这个新的柱子会进一步增加我们的矩形的宽度。因此，我们的原始假设是正确的。
为了确定柱子 A 能够扩展的最大矩形面积，我们只需找到它左边和右边的第一个比它小的柱子，然后计算这两个柱子之间的宽度与 A 的高度的乘积。
基于上述两个定理，我们发现，只要求出每个柱子左右两边第一个比它低的柱子位置，然后就可以算出这个柱子所能形成的最大矩形面积——柱子的高度 * 左右两边比它低的柱子的距离。
但是，我们不打算采用暴力算法的方式去寻找每个柱子左右两边的第一个比它低的柱子，因为每次都需要遍历所有的柱子才能确定，效率是非常差的。
有没有好的办法呢？
有，单调栈。
什么是单调栈呢？
顾名思义，单调栈就是满足单调性的栈结构。与单调队列相比，单调栈只在一端进行进和出。不熟悉的球友可以到**OI Wiki **上看一眼。
我这里再进一步做一些说明。
栈是一种受限的数据结构， 体现在只允许新的内容从一个方向插入或删除，这个方向我们叫栈顶，而从其他位置获取内容是不被允许的。
栈最显著的特征就是 LIFO(Last In, First Out - 后进先出)
举个例子：
栈就像是一个放书本的抽屉，进栈的操作就好比是向抽屉里放一本书，新进去的书永远在最上层，而退栈则相当于从里往外拿书本，永远是从最上层开始拿，所以拿出来的永远是最后进去的那一个。
栈本来就是一种受限的数据结构了，单调栈在此基础上又受限了一次（受限++）。
单调栈要求栈中的元素是单调递增或者单调递减的。
这里我用 [a,b,c] 表示一个栈。 其中左侧为栈底，右侧为栈顶。单调增还是单调减取决于出栈顺序。如果出栈的元素是单调增的，那就是单调递增栈，如果出栈的元素是单调减的，那就是单调递减栈。
比如：
- [1,2,3,4] 就是一个单调递减栈（因为此时的出栈顺序是 4，3，2，1。
- [3,2,1] 就是一个单调递增栈
- [1,3,2] 就不是一个合法的单调栈
举个例子。
比如我们需要依次将数组 [1,3,4,5,2,9,6] 压入单调栈。
- 首先压入 1，此时的栈为：[1]
- 继续压入 3，此时的栈为：[1,3]
- 继续压入 4，此时的栈为：[1,3,4]
- 继续压入 5，此时的栈为：[1,3,4,5]
- 如果继续压入 2，此时的栈为：[1,3,4,5,2] 不满足单调递减栈的特性， 因此需要调整。如何调整？由于栈只有 pop 操作，因此我们只好不断 pop，直到满足单调递减为止。
- 上面其实我们并没有压入 2，而是先 pop，pop 到压入 2 依然可以保持单调递减再 压入 2，此时的栈为：[1,2]
- 继续压入 9，此时的栈为：[1,2,9]
- 如果继续压入 6，则不满足单调递减栈的特性， 我们故技重施，不断 pop，直到满足单调递减为止。此时的栈为：[1,2,6]
单调栈有什么用呢？单调栈一般用于在线性时间内找出每个元素前后第一个比它大/小的元素。
为什么单调栈能在线性时间内做到呢？
我们来看看单调栈最重要的操作——插入。
假设现在的单调栈为自栈底到栈顶依次递增的单调栈。
我们要将一个元素插入单调栈，为了维护栈内的单调性，我们就要依次将栈顶的各个比它高的元素出栈，例如：
我们要将 2 这个元素插入栈中，并且保持栈的单调递增，就必须将栈顶的4,3,2依次弹出，只有这样子才能维持栈的单调性。
这跟我们求左右两侧第一个比当前柱子低的柱子有什么关系呢？
我们来分析单调栈，当一个元素出栈的时候，把它挤掉的这个元素（也就是即将要插入的元素），正是它右边第一个比它小的元素（从左往右遍历的情况下）。
单调栈的时间复杂度应该怎么计算呢？
如果时间复杂度还是很大，即便这种方法很巧妙，也无济于事，对吧？
因为每个元素只会被压入栈一次和弹出栈一次，所以时间复杂度仅为。
好，问题迎刃而解，我们可以采用单调栈来愉快的求出每个元素左右两侧的第一个比它小的元素了（求左边时，只需要从右往左遍历即可）。
class Solution {
// 声明一个栈，用来保存柱子的索引 Stack
// 分别存储每个柱子左边和右边第一个小于它的柱子的位置 int[] lefLower = new int[heights.length]; int[] rigLower = new int[heights.length];
// 初始化，默认左边界为-1，右边界为heights.length Arrays.fill(lefLower,-1); Arrays.fill(rigLower,heights.length);
// 找每个柱子的右边界 for(int i = 0; i < heights.length; i++) { while (!s.empty() && heights[s.peek()] > heights[i]) { rigLower[s.pop()] = i; } s.push(i); }
// 清空栈，为找左边界做准备 s = new Stack<>();
// 找每个柱子的左边界 for (int i = heights.length - 1; i >= 0; i--) { while(!s.empty() && heights[s.peek()] > heights[i]) { lefLower[s.pop()] = i; } s.push(i); }
// 对于每一个柱子，求其能够扩展的最大矩形面积 int res = 0; for(int i = 0; i < heights.length; i++) { res = Math.max(res, (rigLower[i] - lefLower[i] - 1) * heights[i]); }
// 返回结果 return res; }}
由于遍历了两遍，所以效率一般。
能不能优化一下呢？
当然可以！
其实在所有的大于等于自己的元素出栈之后，剩下的那个，就是左边的第一个比自己小的元素！这样子就不需要从右到左再遍历一次了。
class Solution {
// 定义单调栈，栈内元素是柱子的索引，栈内索引对应的高度是单调递增的 Stack
果然效率有所提升。
我们使用以下的柱状图来模拟一下：
heights = [2, 1, 5, 6, 2, 3]
首先，画出对应的柱状图，如下：
现在，让我们逐步使用单调栈来求解。
- 初始化：
- 创建一个单调递增的栈 stack。
- 遍历每个柱子，当前柱子的索引记为 i。
- 栈：empty
- 第一个柱子 (height = 2, i = 0):
- stack 是空的，所以直接将 i 压入栈。
- 栈：0
- 第二个柱子 (height = 1, i = 1):
- 当前柱子的高度小于栈顶柱子的高度，这意味着我们找到了前一个柱子的右边界。
- 弹出栈顶索引，计算以弹出的柱子为高度的矩形的面积：height = 2, width = 1 -> area = 2。
- 栈：empty
- 继续看栈，现在它是空的，所以压入当前柱子 i。
- 栈：1
- 第三个柱子 (height = 5, i = 2):
- 当前柱子的高度大于栈顶柱子的高度，压入 i。
- 栈：1 2
- 第四个柱子 (height = 6, i = 3):
- 同上，压入 i。
- 栈：1 2 3
- 第五个柱子 (height = 2, i = 4):
- 当前柱子的高度小于栈顶柱子的高度，所以我们找到了前一个柱子的右边界。
- 弹出栈顶索引，计算面积：height = 6, width = 1 -> area = 6。
- 栈：1 2
- 继续比较，当前柱子仍然小于新的栈顶柱子。弹出并计算面积：height = 5, width = 2 -> area = 10。
- 栈：1
- 压入当前柱子 i。
- 栈：1 4
- 第六个柱子 (height = 3, i = 5):
- 当前柱子的高度大于栈顶柱子的高度，压入 i。
- 栈：1 4 5
在这个例子中，我们找到的最大面积是 10。
通过这个详细的例子，你可以看到单调栈如何有效地帮助我们找到每个柱子的左边界和右边界，并计算每个矩形的面积。
总结
单调栈经常用于求解每个元素遍历顺序之前/后的第一个比自身小/大的元素，也可以用于离线解决 RMQ 问题（区间最值问题）。
单调栈在解决这类问题时是非常有用的，因为它可以帮助我们迅速找到数组中的某个元素左侧和右侧第一个小于它的元素。在“柱状图中最大的矩形”这个问题中，对于每一个柱子，我们都想知道它左侧和右侧第一个高度小于它的柱子是哪些。这就是单调栈发挥作用的地方。
为什么要找这两个柱子呢？因为这两个柱子决定了当前柱子的宽度，从而可以计算出以当前柱子为高度的矩形的面积。
下面我们来看如何将求解矩形面积的问题转换为使用单调栈：
- 想象一个矩形的高度是当前柱子的高度。为了使这个矩形的面积最大化，我们需要扩展这个矩形的宽度。我们可以向左和向右扩展，直到遇到一个比当前柱子矮的柱子为止。
- 左边界和右边界的确定：左边界是左边第一个高度小于当前柱子的柱子；右边界是右边第一个高度小于当前柱子的柱子。
- 为什么使用单调栈：我们可以使用一个单调递增的栈来帮助确定每个柱子的左边界和右边界。从左到右遍历每个柱子，将柱子的索引压入栈中。当遇到一个高度小于栈顶柱子的柱子时，我们知道我们找到了栈顶柱子的右边界。为了找到左边界，我们可以继续从栈中弹出柱子，直到栈顶柱子的高度小于当前柱子。
- 计算面积：对于每个柱子，我们都能找到它的左边界和右边界，所以我们可以计算以该柱子为高度的矩形的面积。最后，我们在所有的矩形面积中找到最大的那个。
综上，单调栈提供了一种高效的方法来找到柱状图中每个柱子的左边界和右边界，从而帮助我们计算出最大的矩形面积。
力扣链接：https://leetcode.cn/problems/largest-rectangle-in-histogram/
一步一个脚印
不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。
PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。
一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 3500 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！
本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记），访问地址和密码：https://t.zsxq.com/6iuzn6I
题意
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
难度
困难
示例
示例1：
输入：heights = [2,1,5,6,2,3]
解释：最大的矩形为图中红色区域，面积为 10
示例2：
输入： heights = [2,4]
分析
这题看上去很难，也确实是一道困难题，但实际上我们可以通过几条定理的逐步证明，来将它拆分成一道简单题。
我们先把柱子的高度和矩形的“高度”都称为l，把矩形的“宽度”，也就是矩形在x轴上的距离，称为r。
定理1：面积最大的矩形的高度l，必然和一个柱子的高度l相等。
证明：
这个问题的关键在于，当我们选择一个柱子的高度 ( h ) 作为矩形的高度时，我们总是希望该矩形尽可能地在左右两边扩展，以获得最大的面积。
我们来反证法来证明这个结论：
假设存在一个矩形，其面积是最大的，高度为 ( h )，但是在柱状图中没有任何一个柱子的高度正好为 ( h )。那么这个矩形的高度 ( h ) 是怎么来的呢？
- 由于矩形的高度 ( h ) 必然是由两个柱子（或多个）的最小值决定的。设这两个柱子的高度分别为 ( h1 ) 和 ( h2 ) （其中 ( h1 \geq h ) 和 ( h2 \geq h )），它们之间可能还有其他高度的柱子。但由于这个矩形的高度为 ( h )，我们可以知道 ( h1 ) 和 ( h2 ) 之间的所有柱子的高度都不小于 ( h )。
- 如果 ( h1 ) 或 ( h2 ) 中的任何一个高度大于 ( h )，那么我们完全可以选择高度 ( h1 ) 或 ( h2 ) 中的较小者作为矩形的高度，并保持矩形的宽度不变，这样得到的矩形面积肯定会比高度为 ( h ) 的矩形面积更大。这与假设矛盾，因为我们假设了高度为 ( h ) 的矩形面积是最大的。
由此，我们可以得出结论：面积最大的矩形的高度必然和柱状图中的某个柱子的高度相等。
定理2：每个柱子能扩展的最大矩形面积的“宽度”，取决于它左边和右边延伸出去的第一个比它小的柱子。
证明：
这个观点可以通过反证法来解释：
假设我们有柱子 A，其高度为 h。为了确定柱子 A 能够扩展的最大矩形面积的“宽度”，我们要在它的左边和右边查找第一个高度小于 h 的柱子。
- 左边：假设柱子 A 的左边有一个柱子 B，它的高度也是 h 或更高，那么以 A 为高度的矩形可以向左扩展到 B，因为 B 的高度不会限制 A 所形成的矩形的高度。但如果 B 的左边是一个比 h 低的柱子 C，那么 C 就会限制以 A 为高度的矩形向左的扩展。所以，我们可以说 A 能够扩展的最大矩形的“宽度”（在左边）取决于它左边的第一个比它小的柱子 C。
- 右边：类似地，如果柱子 A 的右边有一个柱子 D，其高度也是 h 或更高，那么以 A 为高度的矩形可以向右扩展到 D。但如果 D 的右边是一个比 h 低的柱子 E，那么 E 会限制以 A 为高度的矩形向右的扩展。因此，A 能够扩展的最大矩形的“宽度”（在右边）取决于它右边的第一个比它小的柱子 E。
反证：假设 A 能够扩展的最大矩形的宽度不取决于它左边和右边的第一个比它小的柱子。那么这意味着我们可以继续向左/右扩展该矩形而不受任何限制，直到遇到另一个高度为 h 或更高的柱子，但这与我们的假设矛盾，因为这个新的柱子会进一步增加我们的矩形的宽度。因此，我们的原始假设是正确的。
为了确定柱子 A 能够扩展的最大矩形面积，我们只需找到它左边和右边的第一个比它小的柱子，然后计算这两个柱子之间的宽度与 A 的高度的乘积。
基于上述两个定理，我们发现，只要求出每个柱子左右两边第一个比它低的柱子位置，然后就可以算出这个柱子所能形成的最大矩形面积——柱子的高度 * 左右两边比它低的柱子的距离。
但是，我们不打算采用暴力算法的方式去寻找每个柱子左右两边的第一个比它低的柱子，因为每次都需要遍历所有的柱子才能确定，效率是非常差的。
有没有好的办法呢？
有，单调栈。
什么是单调栈呢？
顾名思义，单调栈就是满足单调性的栈结构。与单调队列相比，单调栈只在一端进行进和出。不熟悉的球友可以到**OI Wiki **上看一眼。
我这里再进一步做一些说明。
栈是一种受限的数据结构， 体现在只允许新的内容从一个方向插入或删除，这个方向我们叫栈顶，而从其他位置获取内容是不被允许的。
栈最显著的特征就是 LIFO(Last In, First Out - 后进先出)
举个例子：
栈就像是一个放书本的抽屉，进栈的操作就好比是向抽屉里放一本书，新进去的书永远在最上层，而退栈则相当于从里往外拿书本，永远是从最上层开始拿，所以拿出来的永远是最后进去的那一个。
栈本来就是一种受限的数据结构了，单调栈在此基础上又受限了一次（受限++）。
单调栈要求栈中的元素是单调递增或者单调递减的。
这里我用 [a,b,c] 表示一个栈。 其中左侧为栈底，右侧为栈顶。单调增还是单调减取决于出栈顺序。如果出栈的元素是单调增的，那就是单调递增栈，如果出栈的元素是单调减的，那就是单调递减栈。
比如：
- [1,2,3,4] 就是一个单调递减栈（因为此时的出栈顺序是 4，3，2，1。
- [3,2,1] 就是一个单调递增栈
- [1,3,2] 就不是一个合法的单调栈
举个例子。
比如我们需要依次将数组 [1,3,4,5,2,9,6] 压入单调栈。
- 首先压入 1，此时的栈为：[1]
- 继续压入 3，此时的栈为：[1,3]
- 继续压入 4，此时的栈为：[1,3,4]
- 继续压入 5，此时的栈为：[1,3,4,5]
- 如果继续压入 2，此时的栈为：[1,3,4,5,2] 不满足单调递减栈的特性， 因此需要调整。如何调整？由于栈只有 pop 操作，因此我们只好不断 pop，直到满足单调递减为止。
- 上面其实我们并没有压入 2，而是先 pop，pop 到压入 2 依然可以保持单调递减再 压入 2，此时的栈为：[1,2]
- 继续压入 9，此时的栈为：[1,2,9]
- 如果继续压入 6，则不满足单调递减栈的特性， 我们故技重施，不断 pop，直到满足单调递减为止。此时的栈为：[1,2,6]
单调栈有什么用呢？单调栈一般用于在线性时间内找出每个元素前后第一个比它大/小的元素。
为什么单调栈能在线性时间内做到呢？
我们来看看单调栈最重要的操作——插入。
假设现在的单调栈为自栈底到栈顶依次递增的单调栈。
我们要将一个元素插入单调栈，为了维护栈内的单调性，我们就要依次将栈顶的各个比它高的元素出栈，例如：
我们要将 2 这个元素插入栈中，并且保持栈的单调递增，就必须将栈顶的4,3,2依次弹出，只有这样子才能维持栈的单调性。
这跟我们求左右两侧第一个比当前柱子低的柱子有什么关系呢？
我们来分析单调栈，当一个元素出栈的时候，把它挤掉的这个元素（也就是即将要插入的元素），正是它右边第一个比它小的元素（从左往右遍历的情况下）。
单调栈的时间复杂度应该怎么计算呢？
如果时间复杂度还是很大，即便这种方法很巧妙，也无济于事，对吧？
因为每个元素只会被压入栈一次和弹出栈一次，所以时间复杂度仅为。
好，问题迎刃而解，我们可以采用单调栈来愉快的求出每个元素左右两侧的第一个比它小的元素了（求左边时，只需要从右往左遍历即可）。
class Solution {
// 声明一个栈，用来保存柱子的索引 Stack
// 分别存储每个柱子左边和右边第一个小于它的柱子的位置 int[] lefLower = new int[heights.length]; int[] rigLower = new int[heights.length];
// 初始化，默认左边界为-1，右边界为heights.length Arrays.fill(lefLower,-1); Arrays.fill(rigLower,heights.length);
// 找每个柱子的右边界 for(int i = 0; i < heights.length; i++) { while (!s.empty() && heights[s.peek()] > heights[i]) { rigLower[s.pop()] = i; } s.push(i); }
// 清空栈，为找左边界做准备 s = new Stack<>();
// 找每个柱子的左边界 for (int i = heights.length - 1; i >= 0; i--) { while(!s.empty() && heights[s.peek()] > heights[i]) { lefLower[s.pop()] = i; } s.push(i); }
// 对于每一个柱子，求其能够扩展的最大矩形面积 int res = 0; for(int i = 0; i < heights.length; i++) { res = Math.max(res, (rigLower[i] - lefLower[i] - 1) * heights[i]); }
// 返回结果 return res; }}
由于遍历了两遍，所以效率一般。
能不能优化一下呢？
当然可以！
其实在所有的大于等于自己的元素出栈之后，剩下的那个，就是左边的第一个比自己小的元素！这样子就不需要从右到左再遍历一次了。
class Solution {
// 定义单调栈，栈内元素是柱子的索引，栈内索引对应的高度是单调递增的 Stack
果然效率有所提升。
我们使用以下的柱状图来模拟一下：
heights = [2, 1, 5, 6, 2, 3]
首先，画出对应的柱状图，如下：
现在，让我们逐步使用单调栈来求解。
- 初始化：
- 创建一个单调递增的栈 stack。
- 遍历每个柱子，当前柱子的索引记为 i。
- 栈：empty
- 第一个柱子 (height = 2, i = 0):
- stack 是空的，所以直接将 i 压入栈。
- 栈：0
- 第二个柱子 (height = 1, i = 1):
- 当前柱子的高度小于栈顶柱子的高度，这意味着我们找到了前一个柱子的右边界。
- 弹出栈顶索引，计算以弹出的柱子为高度的矩形的面积：height = 2, width = 1 -> area = 2。
- 栈：empty
- 继续看栈，现在它是空的，所以压入当前柱子 i。
- 栈：1
- 第三个柱子 (height = 5, i = 2):
- 当前柱子的高度大于栈顶柱子的高度，压入 i。
- 栈：1 2
- 第四个柱子 (height = 6, i = 3):
- 同上，压入 i。
- 栈：1 2 3
- 第五个柱子 (height = 2, i = 4):
- 当前柱子的高度小于栈顶柱子的高度，所以我们找到了前一个柱子的右边界。
- 弹出栈顶索引，计算面积：height = 6, width = 1 -> area = 6。
- 栈：1 2
- 继续比较，当前柱子仍然小于新的栈顶柱子。弹出并计算面积：height = 5, width = 2 -> area = 10。
- 栈：1
- 压入当前柱子 i。
- 栈：1 4
- 第六个柱子 (height = 3, i = 5):
- 当前柱子的高度大于栈顶柱子的高度，压入 i。
- 栈：1 4 5
在这个例子中，我们找到的最大面积是 10。
通过这个详细的例子，你可以看到单调栈如何有效地帮助我们找到每个柱子的左边界和右边界，并计算每个矩形的面积。
总结
单调栈经常用于求解每个元素遍历顺序之前/后的第一个比自身小/大的元素，也可以用于离线解决 RMQ 问题（区间最值问题）。
单调栈在解决这类问题时是非常有用的，因为它可以帮助我们迅速找到数组中的某个元素左侧和右侧第一个小于它的元素。在“柱状图中最大的矩形”这个问题中，对于每一个柱子，我们都想知道它左侧和右侧第一个高度小于它的柱子是哪些。这就是单调栈发挥作用的地方。
为什么要找这两个柱子呢？因为这两个柱子决定了当前柱子的宽度，从而可以计算出以当前柱子为高度的矩形的面积。
下面我们来看如何将求解矩形面积的问题转换为使用单调栈：
- 想象一个矩形的高度是当前柱子的高度。为了使这个矩形的面积最大化，我们需要扩展这个矩形的宽度。我们可以向左和向右扩展，直到遇到一个比当前柱子矮的柱子为止。
- 左边界和右边界的确定：左边界是左边第一个高度小于当前柱子的柱子；右边界是右边第一个高度小于当前柱子的柱子。
- 为什么使用单调栈：我们可以使用一个单调递增的栈来帮助确定每个柱子的左边界和右边界。从左到右遍历每个柱子，将柱子的索引压入栈中。当遇到一个高度小于栈顶柱子的柱子时，我们知道我们找到了栈顶柱子的右边界。为了找到左边界，我们可以继续从栈中弹出柱子，直到栈顶柱子的高度小于当前柱子。
- 计算面积：对于每个柱子，我们都能找到它的左边界和右边界，所以我们可以计算以该柱子为高度的矩形的面积。最后，我们在所有的矩形面积中找到最大的那个。
综上，单调栈提供了一种高效的方法来找到柱状图中每个柱子的左边界和右边界，从而帮助我们计算出最大的矩形面积。
力扣链接：https://leetcode.cn/problems/largest-rectangle-in-histogram/
一步一个脚印
不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。
PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。
一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 3500 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！
本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记），访问地址和密码：https://t.zsxq.com/6iuzn6I
题意
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
难度
困难
示例
示例1：
输入：heights = [2,1,5,6,2,3]
解释：最大的矩形为图中红色区域，面积为 10
示例2：
输入： heights = [2,4]
分析
这题看上去很难，也确实是一道困难题，但实际上我们可以通过几条定理的逐步证明，来将它拆分成一道简单题。
我们先把柱子的高度和矩形的“高度”都称为l，把矩形的“宽度”，也就是矩形在x轴上的距离，称为r。
定理1：面积最大的矩形的高度l，必然和一个柱子的高度l相等。
证明：
这个问题的关键在于，当我们选择一个柱子的高度 ( h ) 作为矩形的高度时，我们总是希望该矩形尽可能地在左右两边扩展，以获得最大的面积。
我们来反证法来证明这个结论：
假设存在一个矩形，其面积是最大的，高度为 ( h )，但是在柱状图中没有任何一个柱子的高度正好为 ( h )。那么这个矩形的高度 ( h ) 是怎么来的呢？
- 由于矩形的高度 ( h ) 必然是由两个柱子（或多个）的最小值决定的。设这两个柱子的高度分别为 ( h1 ) 和 ( h2 ) （其中 ( h1 \geq h ) 和 ( h2 \geq h )），它们之间可能还有其他高度的柱子。但由于这个矩形的高度为 ( h )，我们可以知道 ( h1 ) 和 ( h2 ) 之间的所有柱子的高度都不小于 ( h )。
- 如果 ( h1 ) 或 ( h2 ) 中的任何一个高度大于 ( h )，那么我们完全可以选择高度 ( h1 ) 或 ( h2 ) 中的较小者作为矩形的高度，并保持矩形的宽度不变，这样得到的矩形面积肯定会比高度为 ( h ) 的矩形面积更大。这与假设矛盾，因为我们假设了高度为 ( h ) 的矩形面积是最大的。
由此，我们可以得出结论：面积最大的矩形的高度必然和柱状图中的某个柱子的高度相等。
定理2：每个柱子能扩展的最大矩形面积的“宽度”，取决于它左边和右边延伸出去的第一个比它小的柱子。
证明：
这个观点可以通过反证法来解释：
假设我们有柱子 A，其高度为 h。为了确定柱子 A 能够扩展的最大矩形面积的“宽度”，我们要在它的左边和右边查找第一个高度小于 h 的柱子。
- 左边：假设柱子 A 的左边有一个柱子 B，它的高度也是 h 或更高，那么以 A 为高度的矩形可以向左扩展到 B，因为 B 的高度不会限制 A 所形成的矩形的高度。但如果 B 的左边是一个比 h 低的柱子 C，那么 C 就会限制以 A 为高度的矩形向左的扩展。所以，我们可以说 A 能够扩展的最大矩形的“宽度”（在左边）取决于它左边的第一个比它小的柱子 C。
- 右边：类似地，如果柱子 A 的右边有一个柱子 D，其高度也是 h 或更高，那么以 A 为高度的矩形可以向右扩展到 D。但如果 D 的右边是一个比 h 低的柱子 E，那么 E 会限制以 A 为高度的矩形向右的扩展。因此，A 能够扩展的最大矩形的“宽度”（在右边）取决于它右边的第一个比它小的柱子 E。
反证：假设 A 能够扩展的最大矩形的宽度不取决于它左边和右边的第一个比它小的柱子。那么这意味着我们可以继续向左/右扩展该矩形而不受任何限制，直到遇到另一个高度为 h 或更高的柱子，但这与我们的假设矛盾，因为这个新的柱子会进一步增加我们的矩形的宽度。因此，我们的原始假设是正确的。
为了确定柱子 A 能够扩展的最大矩形面积，我们只需找到它左边和右边的第一个比它小的柱子，然后计算这两个柱子之间的宽度与 A 的高度的乘积。
基于上述两个定理，我们发现，只要求出每个柱子左右两边第一个比它低的柱子位置，然后就可以算出这个柱子所能形成的最大矩形面积——柱子的高度 * 左右两边比它低的柱子的距离。
但是，我们不打算采用暴力算法的方式去寻找每个柱子左右两边的第一个比它低的柱子，因为每次都需要遍历所有的柱子才能确定，效率是非常差的。
有没有好的办法呢？
有，单调栈。
什么是单调栈呢？
顾名思义，单调栈就是满足单调性的栈结构。与单调队列相比，单调栈只在一端进行进和出。不熟悉的球友可以到**OI Wiki **上看一眼。
我这里再进一步做一些说明。
栈是一种受限的数据结构， 体现在只允许新的内容从一个方向插入或删除，这个方向我们叫栈顶，而从其他位置获取内容是不被允许的。
栈最显著的特征就是 LIFO(Last In, First Out - 后进先出)
举个例子：
栈就像是一个放书本的抽屉，进栈的操作就好比是向抽屉里放一本书，新进去的书永远在最上层，而退栈则相当于从里往外拿书本，永远是从最上层开始拿，所以拿出来的永远是最后进去的那一个。
栈本来就是一种受限的数据结构了，单调栈在此基础上又受限了一次（受限++）。
单调栈要求栈中的元素是单调递增或者单调递减的。
这里我用 [a,b,c] 表示一个栈。 其中左侧为栈底，右侧为栈顶。单调增还是单调减取决于出栈顺序。如果出栈的元素是单调增的，那就是单调递增栈，如果出栈的元素是单调减的，那就是单调递减栈。
比如：
- [1,2,3,4] 就是一个单调递减栈（因为此时的出栈顺序是 4，3，2，1。
- [3,2,1] 就是一个单调递增栈
- [1,3,2] 就不是一个合法的单调栈
举个例子。
比如我们需要依次将数组 [1,3,4,5,2,9,6] 压入单调栈。
- 首先压入 1，此时的栈为：[1]
- 继续压入 3，此时的栈为：[1,3]
- 继续压入 4，此时的栈为：[1,3,4]
- 继续压入 5，此时的栈为：[1,3,4,5]
- 如果继续压入 2，此时的栈为：[1,3,4,5,2] 不满足单调递减栈的特性， 因此需要调整。如何调整？由于栈只有 pop 操作，因此我们只好不断 pop，直到满足单调递减为止。
- 上面其实我们并没有压入 2，而是先 pop，pop 到压入 2 依然可以保持单调递减再 压入 2，此时的栈为：[1,2]
- 继续压入 9，此时的栈为：[1,2,9]
- 如果继续压入 6，则不满足单调递减栈的特性， 我们故技重施，不断 pop，直到满足单调递减为止。此时的栈为：[1,2,6]
单调栈有什么用呢？单调栈一般用于在线性时间内找出每个元素前后第一个比它大/小的元素。
为什么单调栈能在线性时间内做到呢？
我们来看看单调栈最重要的操作——插入。
假设现在的单调栈为自栈底到栈顶依次递增的单调栈。
我们要将一个元素插入单调栈，为了维护栈内的单调性，我们就要依次将栈顶的各个比它高的元素出栈，例如：
我们要将 2 这个元素插入栈中，并且保持栈的单调递增，就必须将栈顶的4,3,2依次弹出，只有这样子才能维持栈的单调性。
这跟我们求左右两侧第一个比当前柱子低的柱子有什么关系呢？
我们来分析单调栈，当一个元素出栈的时候，把它挤掉的这个元素（也就是即将要插入的元素），正是它右边第一个比它小的元素（从左往右遍历的情况下）。
单调栈的时间复杂度应该怎么计算呢？
如果时间复杂度还是很大，即便这种方法很巧妙，也无济于事，对吧？
因为每个元素只会被压入栈一次和弹出栈一次，所以时间复杂度仅为。
好，问题迎刃而解，我们可以采用单调栈来愉快的求出每个元素左右两侧的第一个比它小的元素了（求左边时，只需要从右往左遍历即可）。
class Solution {
// 声明一个栈，用来保存柱子的索引 Stack
// 分别存储每个柱子左边和右边第一个小于它的柱子的位置 int[] lefLower = new int[heights.length]; int[] rigLower = new int[heights.length];
// 初始化，默认左边界为-1，右边界为heights.length Arrays.fill(lefLower,-1); Arrays.fill(rigLower,heights.length);
// 找每个柱子的右边界 for(int i = 0; i < heights.length; i++) { while (!s.empty() && heights[s.peek()] > heights[i]) { rigLower[s.pop()] = i; } s.push(i); }
// 清空栈，为找左边界做准备 s = new Stack<>();
// 找每个柱子的左边界 for (int i = heights.length - 1; i >= 0; i--) { while(!s.empty() && heights[s.peek()] > heights[i]) { lefLower[s.pop()] = i; } s.push(i); }
// 对于每一个柱子，求其能够扩展的最大矩形面积 int res = 0; for(int i = 0; i < heights.length; i++) { res = Math.max(res, (rigLower[i] - lefLower[i] - 1) * heights[i]); }
// 返回结果 return res; }}
由于遍历了两遍，所以效率一般。
能不能优化一下呢？
当然可以！
其实在所有的大于等于自己的元素出栈之后，剩下的那个，就是左边的第一个比自己小的元素！这样子就不需要从右到左再遍历一次了。
class Solution {
// 定义单调栈，栈内元素是柱子的索引，栈内索引对应的高度是单调递增的 Stack
果然效率有所提升。
我们使用以下的柱状图来模拟一下：
heights = [2, 1, 5, 6, 2, 3]
首先，画出对应的柱状图，如下：
现在，让我们逐步使用单调栈来求解。
- 初始化：
- 创建一个单调递增的栈 stack。
- 遍历每个柱子，当前柱子的索引记为 i。
- 栈：empty
- 第一个柱子 (height = 2, i = 0):
- stack 是空的，所以直接将 i 压入栈。
- 栈：0
- 第二个柱子 (height = 1, i = 1):
- 当前柱子的高度小于栈顶柱子的高度，这意味着我们找到了前一个柱子的右边界。
- 弹出栈顶索引，计算以弹出的柱子为高度的矩形的面积：height = 2, width = 1 -> area = 2。
- 栈：empty
- 继续看栈，现在它是空的，所以压入当前柱子 i。
- 栈：1
- 第三个柱子 (height = 5, i = 2):
- 当前柱子的高度大于栈顶柱子的高度，压入 i。
- 栈：1 2
- 第四个柱子 (height = 6, i = 3):
- 同上，压入 i。
- 栈：1 2 3
- 第五个柱子 (height = 2, i = 4):
- 当前柱子的高度小于栈顶柱子的高度，所以我们找到了前一个柱子的右边界。
- 弹出栈顶索引，计算面积：height = 6, width = 1 -> area = 6。
- 栈：1 2
- 继续比较，当前柱子仍然小于新的栈顶柱子。弹出并计算面积：height = 5, width = 2 -> area = 10。
- 栈：1
- 压入当前柱子 i。
- 栈：1 4
- 第六个柱子 (height = 3, i = 5):
- 当前柱子的高度大于栈顶柱子的高度，压入 i。
- 栈：1 4 5
在这个例子中，我们找到的最大面积是 10。
通过这个详细的例子，你可以看到单调栈如何有效地帮助我们找到每个柱子的左边界和右边界，并计算每个矩形的面积。
总结
单调栈经常用于求解每个元素遍历顺序之前/后的第一个比自身小/大的元素，也可以用于离线解决 RMQ 问题（区间最值问题）。
单调栈在解决这类问题时是非常有用的，因为它可以帮助我们迅速找到数组中的某个元素左侧和右侧第一个小于它的元素。在“柱状图中最大的矩形”这个问题中，对于每一个柱子，我们都想知道它左侧和右侧第一个高度小于它的柱子是哪些。这就是单调栈发挥作用的地方。
为什么要找这两个柱子呢？因为这两个柱子决定了当前柱子的宽度，从而可以计算出以当前柱子为高度的矩形的面积。
下面我们来看如何将求解矩形面积的问题转换为使用单调栈：
- 想象一个矩形的高度是当前柱子的高度。为了使这个矩形的面积最大化，我们需要扩展这个矩形的宽度。我们可以向左和向右扩展，直到遇到一个比当前柱子矮的柱子为止。
- 左边界和右边界的确定：左边界是左边第一个高度小于当前柱子的柱子；右边界是右边第一个高度小于当前柱子的柱子。
- 为什么使用单调栈：我们可以使用一个单调递增的栈来帮助确定每个柱子的左边界和右边界。从左到右遍历每个柱子，将柱子的索引压入栈中。当遇到一个高度小于栈顶柱子的柱子时，我们知道我们找到了栈顶柱子的右边界。为了找到左边界，我们可以继续从栈中弹出柱子，直到栈顶柱子的高度小于当前柱子。
- 计算面积：对于每个柱子，我们都能找到它的左边界和右边界，所以我们可以计算以该柱子为高度的矩形的面积。最后，我们在所有的矩形面积中找到最大的那个。
综上，单调栈提供了一种高效的方法来找到柱状图中每个柱子的左边界和右边界，从而帮助我们计算出最大的矩形面积。
力扣链接：https://leetcode.cn/problems/largest-rectangle-in-histogram/
一步一个脚印
不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。
PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。
一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 3500 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！
知识星球
扫码加入星球
查看更多优质内容
https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412