柱状图中最大矩形为什么用单调栈？

简化版

柱状图最大矩形要为每根柱子找到左右第一个比它矮的边界。用单调递增栈存下标，当前高度变矮时弹出栈顶，以被弹柱子的高度为矩形高，宽度由新栈顶和当前下标决定。每根柱子进出栈一次，O(n)。

详细版

当柱子 h 被弹出时，说明右边第一个比它矮的位置就是当前下标 i；弹出后新的栈顶就是左边第一个比它矮的位置。于是以 h 为高能扩展的宽度是 i - leftLess - 1。

int largestRectangleArea(int[] heights) {
    int n = heights.length;
    Deque<Integer> stack = new ArrayDeque<>();
    int ans = 0;
    for (int i = 0; i <= n; i++) {
        int cur = (i == n) ? 0 : heights[i];
        while (!stack.isEmpty() && cur < heights[stack.peek()]) {
            int h = heights[stack.pop()];
            int leftLess = stack.isEmpty() ? -1 : stack.peek();
            int width = i - leftLess - 1;
            ans = Math.max(ans, h * width);
        }
        stack.push(i);
    }
    return ans;
}

末尾哨兵高度 0 用来清空栈，避免循环后再单独处理剩余柱子。

完整版教学

一、最大矩形的本质是找边界

一个矩形如果以某根柱子的高度 heights[i] 为高，它能向左右扩展到哪里？答案是：直到遇到第一个比它矮的柱子为止。因为只要区间内所有柱子高度都不低于它，就能组成高度为 heights[i] 的矩形。

例如高度 [2,1,5,6,2,3] 中，以高度 5 为高，左边第一个更矮是 1，右边第一个更矮是 2，所以宽度是 2，对应面积 5 * 2 = 10。

二、为什么单调递增栈能找到左右矮边界

栈内高度保持递增。当当前柱子比栈顶矮时，栈顶柱子的右侧第一个更矮边界就找到了：它就是当前下标。弹出栈顶后，新栈顶就是它左侧第一个更矮边界，因为更高的柱子都已经被弹走，剩下的栈保持递增。

下标:   0 1 2 3 4
高度:   2 1 5 6 2
扫描到高度 2 时，会弹出 6 和 5
对 5 来说: 左矮边界=1，右矮边界=4，宽度=4-1-1=2

这正好把“找左右第一个更小”转成了弹栈时的边界计算。

三、宽度公式怎么推出来

弹出下标 mid 后，当前下标 i 是右侧第一个更矮位置；新的栈顶 leftLess 是左侧第一个更矮位置。能使用高度 heights[mid] 的区间是 (leftLess, i)，不包含两个更矮边界，所以宽度是：

width = i - leftLess - 1
area = heights[mid] * width

如果弹出后栈为空，说明左边没有更矮柱子，令 leftLess = -1。例如 i=4, leftLess=1 时，宽度是 4-1-1=2，覆盖下标 2 和 3。

四、为什么要加哨兵

如果数组最后仍然递增，例如 [1,2,3]，扫描结束时栈里还有柱子没有被更矮的右边界触发。末尾添加一个高度 0 的哨兵，可以强制把所有柱子弹出，并把右边界统一看成 n。

写法	优点	注意点
末尾哨兵 0	主循环内统一结算	循环到 `i <= n`
循环后清栈	不引入虚拟高度	需要额外一段逻辑

面试中推荐哨兵写法，因为边界更集中。

五、相等高度怎么处理

条件写 cur < heights[stack.peek()] 或 cur <= heights[stack.peek()] 都能做，但边界含义略有不同。使用 < 会保留相等高度的旧下标，等到更矮柱子出现时再统一计算；使用 <= 会让新下标替换旧下标。只要宽度公式一致，最大面积不会丢。

为了解释简单，常用严格小于弹栈。遇到 [2,2,2]，哨兵 0 到来时依次计算面积 2、4、6，最终得到 6。

六、常见误区与追问

记忆钩子：被弹出的柱子，左右矮边界在那一刻同时确定；高度用它自己，宽度看两个矮边界中间夹了多少根。

误区：弹栈时用当前高度算面积。 面积的高应该是被弹柱子的高度，当前高度只是右边界触发器。
误区：宽度写成 i - stack.peek()。 两个边界都不能包含，正确是 i - leftLess - 1。
误区：栈里存高度即可。 需要下标计算宽度，存高度会丢位置信息。
追问：为什么是递增栈？ 因为要在遇到更矮柱子时确定更高柱子的右边界。
追问：空栈时左边界为什么是 -1？ 代表左侧没有更矮柱子，矩形可以从下标 0 开始。
追问：复杂度为什么 O(n)？ 每根柱子最多入栈一次、出栈一次，虽然有 while，总弹出次数仍是 n。

七、加强记忆

柱状图最大矩形不要从“枚举左右端点”想，而要从“枚举最低柱子”想。每根柱子作为最低高度时，左右第一个更矮柱子决定宽度；单调递增栈让这个边界在弹栈瞬间出现。记住公式 area = h * (rightLess - leftLess - 1)，这题就不再神秘。

简化版

详细版