LeetCode 84. 柱状图中最大的矩形
目录
题目描述
题意分析
输入是一排紧挨着的柱子，第
i根宽度固定为 1、高度为heights[i]，要求在这排柱子里框出一个完全被填满的矩形，返回它的最大面积。矩形横跨的必须是一段连续下标区间
[l, r]，而它的高度不能超过区间内最矮的那根柱子，所以面积就是「区间长度乘区间最小值」，要求的是这个乘积的最大值。约束信号有三个：柱子高度允许为 0，等于把整排柱子切断，矩形不能跨过去；相邻柱子允许等高，说明会出现大量平台，处理边界时不能默认高度互不相同；数组规模到十万级，$O(n^2)$ 枚举所有区间会超时，必须做到接近线性。
边界上要留意：数组只有一根柱子时答案就是它自身高度；全为 0 时答案为 0；整排等高时答案是「高度乘
n」，这是一个很容易被漏掉的整体矩形。
解法：单调递增栈
核心思路
暴力枚举所有区间需要
O(n²)。更有效的枚举方式是固定第i根柱子作为矩形的最低高度：它能覆盖的最大范围，是左、右两侧第一个严格低于heights[i]的柱子之间。任何矩形的高度都等于区间内某根最低柱子的高度，所以逐根计算这个最大范围不会漏掉最优解。从左到右扫描，用栈保存下标，并维持两条不变量：
- 栈中下标对应的高度从底到顶单调不减；
- 栈中柱子都还没有遇到右侧第一个更矮的位置，因此面积暂不能最终结算。
当当前高度
cur小于栈顶高度时，当前下标i就是栈顶柱子的右侧第一个更矮位置。弹出该下标后，把新栈顶记为left，栈空则记为-1，区间(left, i)的宽度是i - left - 1。若新栈顶与被弹柱等高，这次得到的只是一个较窄但合法的候选；那根更靠左的等高柱稍后会计算覆盖整个平台的候选。每根柱子只在右边界确定时结算一次。扫描结束后仍在栈中的递增柱子没有遇到更矮值，所以在末尾虚拟一根高度为 0 的柱子统一结算。相等高度可以同时留栈：较右的等高柱先得到较窄区间，最左的等高柱最终会覆盖整个平台。
正确性来自“以最低柱为高”的枚举：最低柱唯一时，算法会计算它能扩展到的最大范围；最低柱有多个且等高时，最左边的那根最后弹出并覆盖整个平台。任意最优矩形都对应其中一个候选，因此不会漏掉最大面积。
解题步骤
- 创建存下标的栈，答案初始化为 0。
- 下标从 0 扫到
n；i == n时把当前高度视为 0，作为末尾哨兵。- 当栈顶高度大于当前高度时持续弹栈。被弹柱子的右边界是
i，左边界是弹栈后的新栈顶，栈空则为-1。- 用
height × (i - left - 1)更新最大面积。- 处理完所有更高柱子后，若
i < n，把当前下标入栈。以
[2,1,5,6,2,3]为例，扫描到下标 4 的高度 2 时，先结算高度 6，面积为6 × 1；再结算高度 5，此时新栈顶是下标 1，宽度为4 - 1 - 1 = 2，面积为 10。末尾哨兵再结算剩余柱子，最终答案仍是 10。
代码实现
class Solution {
public int largestRectangleArea(int[] heights) {
int n = heights.length;
int[] stack = new int[n];
int top = -1;
int ans = 0;
for (int i = 0; i <= n; i++) {
int cur = i == n ? 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));
}
if (i < n) {
stack[++top] = i;
}
}
return ans;
}
}
func largestRectangleArea(heights []int) int {
stack := make([]int, 0, len(heights))
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
}
}
if i < len(heights) {
stack = append(stack, i)
}
}
return ans
}
复杂度分析
- 时间复杂度：
O(n)。每个下标最多入栈一次、出栈一次，所有while循环的弹栈次数合计不超过n。- 空间复杂度：
O(n)。高度单调不减时，所有下标会同时留在栈中。
关键点总结
- 把“枚举区间”改成“枚举哪根柱子作为最低高度”，问题就转为求左右第一个更小元素。
- 栈存下标而不是高度，因为矩形宽度依赖位置。
- 弹栈后才读取左边界；宽度对应开区间
(left, i)，所以是i - left - 1。- 末尾哨兵把残留柱子的结算合并进主循环。
- 嵌套
while的总成本是线性的，因为每根柱子只会被弹出一次。
易错点总结
- 宽度少减 1：
[2,1,2]中结算第一根柱子时，左右边界为-1和 1，覆盖宽度只能是 1；写成i - left会虚增一格。- 弹栈前读取左边界：此时拿到的是被结算柱子本身，而不是它左侧第一个更矮的位置，
[2,1,5,6,2,3]会漏掉面积 10。- 没有末尾哨兵或收尾循环：
[1,2,3]全程不触发弹栈，会错误返回 0。- 栈空时把左边界设为 0：最低柱子无法覆盖数组开头；虚拟边界应为
-1。- 栈里只存高度：无法确定左右下标，也就算不出宽度。
- 认为等高柱必须立即弹出：本实现用
>保留等高下标同样正确；若改成>=也能做，但必须重新说明等高边界由后一个下标继承，不能混用两套不变量。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 85. 最大矩形 | 困难 | 逐行把 01 矩阵压成高度数组，把本题当子过程调用 |
| 42. 接雨水 | 困难 | 同样用单调栈，但栈内维持递减，按层横向结算积水 |
| 739. 每日温度 | 中等 | 单调栈的最小形态，只求右侧第一个更大元素的距离 |
| 907. 子数组的最小值之和 | 中等 | 同样枚举「谁当最小值」，但统计的是子数组个数而非面积 |
| 1504. 统计全 1 子矩形 | 中等 | 高度数组上做计数而不是取最值，需要额外的连续段递推 |
| LCR 039. 柱状图中最大的矩形 | 困难 | 与本题完全同构，可用作模板默写的校验 |
| LCR 040. 最大矩形 | 困难 | 输入为字符矩阵，需先处理字符到高度的转换 |
| 补充题 3. 求区间最小数乘区间和的最大值 | 困难 | 把「宽度」换成前缀和之差，要求元素非负才能沿用结论 |