Largest Rectangle in Histogram 是 LeetCode Hot 100 里面一道非常经典的单调栈题。
这道题第一次看时，很多人都会觉得不太好下手。因为题目看起来很直观：
但真正开始做时，很容易卡在一个问题上：
如果以某一根柱子作为高度，它到底能向左和向右扩展到哪里？
这正是整道题的核心。
你给出的这份 Java 代码，使用的是这道题最经典、也非常标准的一种解法：
单调栈 + 预处理左右第一个更小元素
这种写法的核心思想是：
-
对于每一根柱子，找到它左边第一个比它低的位置
-
找到它右边第一个比它低的位置
-
这样它能作为“最矮柱子”支撑的最大宽度就确定了
-
面积也就能直接算出来
本文就结合这段代码，系统地讲一下这道题的思路。
题目介绍
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。 每个柱子的宽度都为 1。
现在要求你求出在这个柱状图中，能够勾勒出的最大矩形面积。
例如：
heights = [2,1,5,6,2,3]
对应的柱状图中，最大矩形面积是：
10
因为可以选择高度为 5 和 6 那两根柱子形成的区域，最优矩形宽度为 2，高度取 5，所以面积为：
5 × 2 = 10
这道题的关键并不是枚举“矩形左边界和右边界”，而是换个角度思考：
如果固定某一根柱子作为矩形的最低高度，它最多能扩展多宽？
示例
示例 1
输入：heights = [2,1,5,6,2,3]
输出：10
最大矩形由中间高度为 5、6 的区域构成，面积为 10。
示例 2
输入：heights = [2,4]
输出：4
因为：
-
只选高度为 2 的两根柱子，面积是
2 × 2 = 4 -
单独选高度为 4 的柱子，面积是
4 × 1 = 4
所以最大面积是 4。
最直接的想法是什么？
如果最开始不考虑优化，一个很自然的思路是：
-
枚举每一个区间
[l, r] -
找出这个区间里的最小高度
-
用：
最小高度 × 区间宽度
计算矩形面积
-
最后取最大值
但问题是，这样做复杂度会比较高。 因为：
-
区间有很多种
-
每个区间还要找最小值
即使做一些优化，整体仍然很容易超时。
所以这道题真正高效的做法，不是从“枚举区间”出发，而是从：
枚举每根柱子作为最矮柱子时，能形成的最大矩形
这个方向入手。
核心思路：以每根柱子为最低高度
假设我们固定某一根柱子 i，它的高度是：
heights[i]
如果让它作为矩形中的最矮柱子，那么这个矩形能向左右扩展的边界取决于什么？
答案是：
-
向左一直扩展，直到遇到第一个比它矮的柱子
-
向右一直扩展，直到遇到第一个比它矮的柱子
也就是说，我们需要知道两件事：
左边界
左边第一个严格小于 heights[i] 的位置
右边界
右边第一个严格小于 heights[i] 的位置
一旦这两个位置找到了，那么以 heights[i] 为最矮柱子的最大宽度就是：
rightLower[i] - leftLower[i] - 1
所以它能形成的最大矩形面积就是：
heights[i] × (rightLower[i] - leftLower[i] - 1)
整道题就转化成：
快速求每个位置左右两边第一个更小元素。
而这正是单调栈最擅长的问题。
为什么用单调栈？
因为我们想找的是：
-
每个位置左边第一个更小元素
-
每个位置右边第一个更小元素
这类“最近更小 / 更大元素”的问题，几乎都是单调栈的典型应用。
在这道题里，我们维护一个 单调递增栈，栈里存的是下标。 这样当遍历到一个新柱子时，如果它比栈顶对应的柱子更低，就说明：
-
它就是那些更高柱子的“右边第一个更小元素”
于是可以不断弹栈并更新右边界。
同时，弹栈结束后，当前栈顶就是当前柱子左边第一个更小元素。
这就是你代码的核心逻辑。
Java 代码
下面是你给出的代码，我这里保留原始逻辑，并加上注释：
class Solution {
public int largestRectangleArea(int[] heights) {
Stack<Integer> s = new Stack<>();
int[] lefLower = new int[heights.length];
int[] rigLower = new int[heights.length];
// 默认右边没有更小元素时，边界设为数组长度
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;
}
// 当前柱子左边第一个更小元素，就是弹栈后栈顶
lefLower[i] = s.empty() ? -1 : s.peek();
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;
}
}
代码拆解
这段代码虽然不算很长，但第一次接触单调栈的人，很容易在 lefLower、rigLower、弹栈逻辑这几个地方绕进去。 下面一步一步来看。
1. 为什么栈里存的是下标，而不是高度？
Stack<Integer> s = new Stack<>();
因为我们最后不仅要知道“有没有更小的元素”，更要知道：
-
左边第一个更小元素的 位置
-
右边第一个更小元素的 位置
只有知道位置，才能算宽度。
如果栈里只存高度，那后面就没法直接计算：
rightLower[i] - leftLower[i] - 1
所以栈里必须存下标。
2. lefLower 和 rigLower 分别表示什么？
int[] lefLower = new int[heights.length];
int[] rigLower = new int[heights.length];
这两个数组是整道题最核心的中间结果。
lefLower[i]
表示：
位置 i 左边第一个严格小于 heights[i] 的下标
如果左边没有更小元素，就记为：
-1
rigLower[i]
表示：
位置 i 右边第一个严格小于 heights[i] 的下标
如果右边没有更小元素，就记为：
heights.length
为什么这样设置默认值？ 因为这样后面算宽度时会非常方便，不需要额外分情况讨论。
3. 为什么要先把 rigLower 全部填成 heights.length？
Arrays.fill(rigLower, heights.length);
因为有些柱子右边可能根本不存在更小元素。
例如：
[1,2,3,4]
其中最后几个柱子右边都没有更小值。
这时我们就把它们的“右边界”视为数组右边界之外的位置：
heights.length
这样在计算宽度时，统一公式仍然成立：
rigLower[i] - lefLower[i] - 1
所以这是一个很常见的边界初始化技巧。
4. 为什么 while 里要弹栈？
while (!s.empty() && heights[s.peek()] > heights[i]) {
rigLower[s.pop()] = i;
}
这是整道题最关键的一段。
我们维护的是一个按高度单调递增的栈。 也就是说，栈顶到栈底对应的柱子高度是递增的。
当当前柱子 heights[i] 比栈顶柱子还低时，说明：
当前柱子就是栈顶柱子右边第一个更小元素。
所以：
-
把栈顶弹出来
-
记录它的右边界是当前
i
而且如果当前柱子还比新的栈顶更低，就继续弹，直到栈重新恢复单调递增。
这一步本质上是在批量确定很多柱子的右边界。
5. 为什么弹栈后栈顶就是当前柱子的左边第一个更小元素？
lefLower[i] = s.empty() ? -1 : s.peek();
因为栈里始终保持“高度单调递增”。
在当前柱子 i 进入栈之前，所有比它高的柱子已经在前面的 while 中被弹掉了。 所以此时留在栈顶的那个柱子，要么：
-
比当前柱子更低
-
要么栈空
并且由于栈顶是离当前位置最近的那个还没被弹掉的位置，所以它正好就是：
左边第一个更小元素
如果栈空，说明左边根本没有更小值，于是记为 -1。
6. 为什么最后面积公式是这样？
(rigLower[i] - lefLower[i] - 1) * heights[i]
因为：
-
lefLower[i]是左边第一个更小的位置 -
rigLower[i]是右边第一个更小的位置
所以在这两个位置之间，中间所有柱子的高度都至少是 heights[i]。
因此，以 heights[i] 为最矮柱子时，它能够支撑的最大宽度就是：
从 lefLower[i] 右边一个位置，到 rigLower[i] 左边一个位置
长度正好是：
rigLower[i] - lefLower[i] - 1
再乘上高度 heights[i]，就是面积。
手动模拟一遍
我们用经典例子来走一下：
heights = [2,1,5,6,2,3]
第一步：求左边和右边第一个更小元素
最终会得到：
lefLower = [-1,-1,1,2,1,4]
rigLower = [1,6,4,4,6,6]
解释几个关键位置：
对于高度 5（下标 2）
-
左边第一个更小元素是下标 1，对应高度 1
-
右边第一个更小元素是下标 4，对应高度 2
所以它的最大宽度是：
4 - 1 - 1 = 2
面积是：
5 × 2 = 10
对于高度 6（下标 3）
-
左边第一个更小元素是下标 2
-
右边第一个更小元素是下标 4
宽度是：
4 - 2 - 1 = 1
面积：
6 × 1 = 6
对于高度 2（下标 4）
-
左边第一个更小元素是下标 1
-
右边没有更小元素，所以是 6
宽度：
6 - 1 - 1 = 4
面积：
2 × 4 = 8
最终所有柱子中最大面积就是：
10
这正好是答案。
为什么这个方法是正确的？
因为对于任意一根柱子 i，如果把它视为某个矩形的最低高度，那么这个矩形能够延伸的最大范围，一定会被：
-
左边第一个更小柱子
-
右边第一个更小柱子
限制住。
在这两个更小柱子之间的所有位置，柱子高度都不低于 heights[i]，所以它们可以一起构成一个以 heights[i] 为高度的矩形。
而超过这两个边界之后，就会遇到更低柱子，矩形再扩展就不合法了。
所以：
-
每根柱子都能对应一个“以它为最矮柱子”的最大矩形
-
所有这些矩形中，最大面积一定就是答案
单调栈的作用，只是帮我们高效求出了每根柱子的左右边界而已。
复杂度分析
时间复杂度
虽然代码里有一个 for 加一个 while，但每个下标最多只会：
-
入栈一次
-
出栈一次
所以整体时间复杂度仍然是：
O(n)
空间复杂度
额外使用了：
-
一个栈
-
两个数组
lefLower和rigLower
所以空间复杂度是：
O(n)
这道题真正想考什么？
这道题表面上是在算面积，但本质上考察的是单调栈的典型应用。
第一，是否能把问题转化成“最近更小元素”
很多人第一次做这题，会一直盯着“矩形”。 但真正的突破口其实是：
以每根柱子为最低高度时，它左右能扩多远？
一旦想到这一步，问题就变成了最近更小元素问题，而这正是单调栈的主场。
第二，是否理解单调栈维护的到底是什么
栈维护的不是答案本身，而是一个单调结构。 借助这个单调结构，我们才能在遍历过程中高效确定很多元素的边界信息。
第三，是否会处理边界默认值
像这题里的：
-
左边没有更小值时记为
-1 -
右边没有更小值时记为
n
这些都是非常经典的技巧，能让后面的公式写得更统一。
和“接雨水”有什么相似之处？
这两题表面不同，但有一个共同点：
-
都是在数组上找某种“范围”
-
都需要借助局部边界信息来计算面积
不过它们的核心思路不一样：
接雨水
更核心的是左右最大值 / 双指针 / 单调栈。
柱状图最大矩形
更核心的是：
左右第一个更小元素
所以这题是单调栈专题里极其经典的一道模板题。
总结
这道题的核心思想可以概括成一句话：
对于每根柱子，找到它左右两边第一个更小元素的位置，这样就能确定它作为最矮柱子时能形成的最大矩形面积。
具体步骤就是：
-
用单调递增栈维护柱子下标
-
在遍历过程中确定每个柱子的右边第一个更小元素
-
弹栈结束后，当前栈顶就是它左边第一个更小元素
-
得到左右边界后，用公式：
(右边界 - 左边界 - 1) × 当前高度
计算面积
-
取所有面积中的最大值
这样就能在：
O(n)
的时间复杂度内解决问题。
这是一道非常经典、也非常值得反复理解的单调栈题。 因为它会让你真正体会到：
-
单调栈到底解决什么问题
-
最近更小元素为什么这么重要
-
看似复杂的范围问题，如何被转化成边界问题
把这道题真正吃透之后，再去看：
-
每日温度
-
下一个更大元素
-
接雨水
-
最大矩形
这些单调栈题时，你会明显更容易抓住套路。
