LeetCode LCR 039. 柱状图中最大的矩形
目录
题目描述
题意分析
输入是一排紧挨着的柱子，第
i根宽度固定为 1、高度为heights[i]，要求在这排柱子里框出一个完全被填满的矩形，返回它的最大面积。矩形横跨的必须是一段连续下标区间
[l, r]，而它的高度不能超过区间内最矮的那根柱子，所以面积就是「区间长度乘区间最小值」，要求的是这个乘积的最大值。约束信号有三个：柱子高度允许为 0，等于把整排柱子切断，矩形不能跨过去；相邻柱子允许等高，说明会出现大量平台，处理边界时不能默认高度互不相同；数组规模到十万级，$O(n^2)$ 枚举所有区间会超时，必须做到接近线性。
边界上要留意：数组只有一根柱子时答案就是它自身高度；全为 0 时答案为 0；整排等高时答案是「高度乘
n」，这是一个很容易被漏掉的整体矩形。
解法：单调递增栈
核心思路
最朴素的想法是枚举左右端点，一边扩张一边维护区间最小值，$O(n^2)$ 次更新，数据一大就崩。瓶颈在于同一个「最矮柱子」被反复重新发现：区间
[3, 9]和[3, 10]的最小值往往是同一根柱子，却各算了一遍。于是换一个枚举维度：不枚举区间，而是枚举「谁当矩形的高」。固定第
i根柱子作为矩形的最矮高度，那么这个矩形能向左伸展到左边第一根比它矮的柱子之后，向右伸展到右边第一根比它矮的柱子之前，宽度就此唯一确定。每根柱子都当一次高，取最大面积，答案不会漏——因为任何最优矩形的高度必然等于它区间内某根柱子的高度，那根柱子被枚举到时得到的宽度只会更宽。问题于是化归为「对每个下标求左右两侧第一个更矮的位置」，这正是单调栈的主场。观察到一个关键现象：当我们从左往右扫描时，如果柱子
a在柱子b左边且a不比b高，那么a就永远挡在b前面，b的左边界只可能落在a或a更右边——比b高的那些左侧柱子，一旦遇到b就再也没有资格当任何后来者的左边界了，可以当场丢弃。因此维持这样一条不变量：栈里存的是下标，且自栈底到栈顶，对应的高度严格递增；同时，栈中任意相邻两个下标之间被弹掉的柱子，高度都不低于上面那个下标对应的高度。这条不变量带来两个直接推论：其一，当扫描到下标
i且heights[i]小于栈顶高度时，i就是栈顶柱子右边第一个更矮的位置；其二，把栈顶弹出后，新的栈顶stack.peek()就是它左边第一个更矮的位置——因为夹在两者之间的柱子已经全被弹掉，而它们只可能比被弹出的柱子更高。由此宽度写成
i - stack.peek() - 1就有了严格解释：矩形真正覆盖的下标区间是左开右开的(stack.peek(), i)，即[stack.peek() + 1, i - 1]，元素个数为(i - 1) - (stack.peek() + 1) + 1 = i - stack.peek() - 1。两个端点本身都是「比我矮」的柱子，撑不起这个高度，必须双双排除，所以要减 1 而不是写成i - stack.peek()。当弹栈后栈已为空，说明左边没有任何比它矮的柱子，左边界视作虚拟下标-1，宽度自然退化为i。最后补一个收尾观察：扫描结束时栈里必然还残留着一批高度递增、始终没等到「更矮者」的柱子。与其在循环外再写一段清算代码，不如在数组末尾虚拟一根高度为 0 的哨兵柱，它比任何柱子都矮，会把栈彻底清空，让所有柱子走同一条结算路径。
解题步骤
- 准备一个存下标的栈和答案变量
ans = 0。存下标而不是存高度，是因为结算宽度时必须知道位置，而高度随时能用heights[下标]反查，存下标信息更全。- 让循环下标
i从 0 走到n（含n），当i == n时把当前高度取作 0。多走这一步就是虚拟哨兵，目的是保证收尾时栈被清空，不必在循环外重复一遍结算逻辑。- 每一步先做结算：当栈非空且栈顶高度严格大于当前高度时，反复弹栈。用严格大于而非大于等于，是为了让等高的柱子暂时留在栈里；等高平台中最右边那根被结算时，左边界会一路穿透到平台之前，宽度依然完整，所以不会漏解。
- 每次弹栈时，取被弹下标对应的高度作为矩形的高，右边界是
i，左边界是弹栈后新的栈顶（栈空则记作-1），宽度为i - 左边界 - 1，用「高乘宽」更新ans。此刻才结算，是因为直到遇见i这根更矮的柱子，它的右边界才第一次被确定下来。- 结算完把
i入栈，进入下一轮。此时当前高度已不小于新栈顶高度，递增不变量得以保持。- 以
[2,1,5,6,2,3]走一遍：i=0，栈空，压入 0，栈为[0]，高度视图[2]。i=1，当前高 1，栈顶高 2 更大，弹出下标 0，高 2，栈已空左边界记-1，宽1-(-1)-1=1，面积 2，ans=2；压入 1，栈[1]，高度[1]。i=2，当前高 5 不小于栈顶高 1，直接压入，栈[1,2]，高度[1,5]。i=3，当前高 6，压入，栈[1,2,3]，高度[1,5,6]。i=4，当前高 2：栈顶高 6 更大，弹出下标 3，左边界为新栈顶 2，宽4-2-1=1，面积 6，ans=6；栈顶变成下标 2 高 5 仍更大，弹出，左边界为新栈顶 1，宽4-1-1=2，面积 10，ans=10；此时栈顶下标 1 高 1 不再大于 2，停止弹栈，压入 4，栈[1,4]，高度[1,2]。i=5，当前高 3 不小于 2，压入，栈[1,4,5]，高度[1,2,3]。i=6触发哨兵，当前高视作 0：弹出下标 5，高 3，左边界 4，宽6-4-1=1，面积 3；弹出下标 4，高 2，左边界 1，宽6-1-1=4，面积 8；弹出下标 1，高 1，栈空左边界记-1，宽6-(-1)-1=6，面积 6。三次都没超过 10，最终答案10，对应高 5、宽 2 的矩形，即下标 2 到 3 这两根柱子。
代码实现
class Solution {
public int largestRectangleArea(int[] heights) {
int[] stack = new int[heights.length + 1];
int top = -1;
int ans = 0;
for (int i = 0; i <= heights.length; i++) {
int cur = i == heights.length ? 0 : heights[i];
while (top >= 0 && heights[stack[top]] > cur) {
// 弹出的柱子以自身高度为矩形最矮高度，左右边界此时已确定。
int height = heights[stack[top--]];
int left = top >= 0 ? stack[top] : -1;
ans = Math.max(ans, height * (i - left - 1));
}
stack[++top] = i;
}
return ans;
}
}
func largestRectangleArea(heights []int) int {
stack := make([]int, 0)
ans := 0
for i := 0; i <= len(heights); i++ {
cur := 0
if i < len(heights) {
cur = heights[i]
}
for len(stack) > 0 && heights[stack[len(stack)-1]] > cur {
// 当前下标是右侧第一个更矮位置，弹栈后栈顶是左侧更矮位置。
height := heights[stack[len(stack)-1]]
stack = stack[:len(stack)-1]
left := -1
if len(stack) > 0 {
left = stack[len(stack)-1]
}
area := height * (i - left - 1)
if area > ans {
ans = area
}
}
stack = append(stack, i)
}
return ans
}
复杂度分析
- 时间复杂度：$O(n)$。外层循环走 $n + 1$ 步，内层的弹栈次数不能按「每轮最多 $n$ 次」去累计，要用摊还的眼光看：每个下标一生只会入栈一次、出栈一次，出栈后再也不会回来，所以整个过程中弹栈总次数至多为 $n$，与外层的 $n + 1$ 步相加仍是线性。
- 空间复杂度：$O(n)$。栈里最多同时存放 $n$ 个下标，出现在整排柱子严格递增时，此时全部柱子都要等到哨兵才被结算。
关键点总结
- 求「区间长度乘区间最小值」的最值，优先把枚举维度从「枚举区间」换成「枚举谁当最小值」，问题立刻退化成求左右两侧第一个更小元素，这是单调栈最典型的触发信号。
- 单调栈的正确性全靠一条不变量撑着：栈内下标对应高度严格递增。写代码前先把不变量说清楚，弹栈时机、左右边界取值、循环条件都会自动确定，不必靠试错凑。
- 栈里存下标而非存值。下标能反查出高度，反之不行，宽度计算又必须依赖下标，所以存下标严格更优。
- 哨兵是消除边界分支的通用手段：末尾补一个「比所有元素都小」的虚拟值，把「循环结束后的收尾清算」并入主循环，代码短了，也少了一处最常见的漏算。
- 面试视角：这题的加分点不在写出代码，而在能否主动说出「每个元素至多进出栈一次，所以是摊还 $O(n)$」，以及能否解释清楚
i - stack.peek() - 1里那个减 1 的来历。面试官通常还会追问两个延伸——若把高度换成「等高时也弹栈」是否仍然正确（正确，等高的重复结算只是多算了几次更窄的矩形，不影响最大值），以及本题如何作为子过程解决 85 题最大矩形（逐行把矩阵压成柱状图高度数组，对每一行调用一次）。
易错点总结
- 错误写法：把宽度写成
i - stack.peek()。以[2,1,2]为例，结算下标 0 的柱子时左边界为-1、右边界i = 1，正确宽度是 1，写成i - (-1) = 2会得到面积 4，而真实答案是 3，宽度整体被放大一格。- 错误写法：不加末尾哨兵，循环只走到
n - 1就结束。以[1,2,3]为例，三根柱子高度递增，从头到尾没有任何一次弹栈，栈内残留三个下标全部未结算，返回 0，正确答案是 3。- 错误写法：加了哨兵却在循环外又写一遍清算逻辑。残留柱子会被结算两次，虽然取最大值时结果常常侥幸不变，但一旦清算段里的左边界取值和主循环不一致，就会算出超过真实面积的答案。
- 错误写法：栈里存高度而不是下标。弹栈时手上只有高度值，无从知道左右边界的位置，宽度只能靠额外数组补记，等于把单调栈的优势又还了回去。
- 错误写法：弹栈后忘了用新栈顶当左边界，仍沿用被弹下标本身或弹栈前的栈顶。以
[2,1,5,6,2,3]为例，结算下标 2（高 5）时正确左边界是 1、宽度 2、面积 10，若误用被弹下标 2 自己，宽度会算成 1，答案退化成 6。- 错误写法：栈为空时不把左边界当作
-1，而是直接跳过结算或取 0。以全局最矮柱子为例，它本该向左伸展到数组开头，跳过它就会漏掉「整排宽度」这一类候选矩形，[1,1,1]会算出 1 而不是 3。- 错误写法：弹栈条件用大于等于且左边界处理不配套。等高柱子被提前弹出后，若左边界仍按「第一个更矮」的语义去理解，中途结算出的宽度会偏小；这种写法要成立必须依赖「最右侧那根等高柱子会补上完整宽度」，把条件改松却不理解为何仍成立，很容易在变形题里出错。
- 错误写法：面积用
int累乘却不留意量级。高度上限乘以长度上限时结果可能超出 32 位范围，这类题在变形版本（如带权柱子）里必须换成 64 位，本题数据虽在安全区间内，但面试中被追问时要能答出判断依据。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 85. 最大矩形 | 困难 | 逐行把 01 矩阵压成高度数组，把本题当子过程调用 |
| 42. 接雨水 | 困难 | 同样用单调栈，但栈内维持递减，按层横向结算积水 |
| 739. 每日温度 | 中等 | 单调栈的最小形态，只求右侧第一个更大元素的距离 |
| 907. 子数组的最小值之和 | 中等 | 同样枚举「谁当最小值」，但统计的是子数组个数而非面积 |
| 1504. 统计全 1 子矩形 | 中等 | 高度数组上做计数而不是取最值，需要额外的连续段递推 |
| LCR 040. 最大矩形 | 困难 | 输入为字符矩阵，需先处理字符到高度的转换 |
| 补充题 3. 求区间最小数乘区间和的最大值 | 困难 | 把「宽度」换成前缀和之差，要求元素非负才能沿用结论 |