84. 柱状图中最大矩形（Largest Rectangle in Histogram）
频次 ★★★★ · 难度 🔴 · 高频：阿里/字节
题目
给定 n 个非负整数表示柱状图每根柱子的高度（宽度均为 1），求柱状图中能勾勒出的最大矩形面积。
示例：
输入: heights = [2,1,5,6,2,3]
输出: 10 (由高度 5、6 的两根柱子构成，宽 2 高 5)
思路
暴力法枚举每个矩形的左右边界是 O(n²)。更优的思路是：以每根柱子的高度为矩形的高，向左右尽量扩展，找到”以它为高度上限”能撑到的最大宽度，取所有柱子里的最大面积。
用单调递增栈维护下标，保持栈内对应的高度递增：
- 遍历到第
i根柱子，如果比栈顶矮，说明栈顶那根柱子往右不能再扩展了（被i挡住了），弹出栈顶结算它能撑起的矩形面积：高度是被弹出的柱子高度，宽度是”新的栈顶下标”和i之间的距离减一。 - 末尾追加一根高度为 0 的哨兵柱子，保证栈中剩余的柱子都能被弹出结算。
代码
public int largestRectangleArea(int[] heights) {
Deque<Integer> stack = new ArrayDeque<>(); // 存下标，对应高度递增
int maxArea = 0;
int n = heights.length;
for (int i = 0; i <= n; i++) {
int h = (i == n) ? 0 : heights[i]; // 末尾哨兵，逼出栈内剩余元素
while (!stack.isEmpty() && h < heights[stack.peek()]) {
int height = heights[stack.pop()];
int width = stack.isEmpty() ? i : i - stack.peek() - 1;
maxArea = Math.max(maxArea, height * width);
}
stack.push(i);
}
return maxArea;
}复杂度
- 时间：O(n) — 每个下标入栈、出栈各一次
- 空间：O(n) — 最坏情况（高度递增）栈存满所有下标
边界条件
- 只有一根柱子：哨兵触发一次弹出结算，宽度为 1，面积等于该柱子高度。
- 所有柱子高度相同（如
[3,3,3]）：只有遇到哨兵 0 时才会连续弹出结算，最终能正确算出”整体宽度 × 高度”的最大面积。 - 高度单调递增（如
[1,2,3]）：栈会一路压入不弹出，直到哨兵才开始结算，是最坏空间情况。
变式
- 最大正方形（矩阵中全 1 的最大正方形，LeetCode 221 题）：可以转化为逐行构造”以每个位置为底的柱状图高度”，再对每一行跑一次本题的算法，取所有行里的最大正方形边长。
- 最大矩形（矩阵中全 1 的最大矩形，LeetCode 85 题）：同样是逐行构造柱状图高度，直接复用本题的单调栈算法求每一行的最大矩形面积，取全局最大值。
易错点
- 宽度计算
stack.isEmpty() ? i : i - stack.peek() - 1：如果栈弹空了，说明这根柱子是当前最矮的，能一直撑到最左边（宽度就是i）；否则宽度是”新栈顶和 i 之间”的柱子数。 - 末尾的哨兵高度 0 不能省略，否则栈里剩下的递增高度不会被结算，会漏算答案。
面试追问
- 为什么要在末尾补一根高度为 0 的柱子？ 如果不补，栈里”高度递增”的柱子在遍历结束后不会被弹出结算（因为没有更矮的柱子触发弹出条件），漏掉这些柱子可能撑起的矩形面积；补一根高度 0 的哨兵能保证所有柱子最终都被结算一次。
- 这题和 739. 每日温度 都用单调栈，核心区别是什么？ 739 题只需要知道”下一个更大元素的位置”，本题不仅要知道”左右两边第一个更矮的柱子在哪”，还要用这两个边界计算出宽度和面积，是单调栈”确定左右边界”这个能力的进一步应用，属于同一类模板但结算逻辑更复杂。