柱状图中最大的矩形：
为什么栈里存下标，宽度看左右两端

以每根柱子为基准，找它的最大跨度。

给定一组柱子的高度，每个柱子的宽度都是 1，求由连续柱子勾勒出的最大矩形面积。矩形的高度不能超过所包含柱子中的最小值。

如果用暴力思路，我们会固定某根柱子作为矩形的高度，然后分别向左、向右扫描，找到左右两边第一个比它更矮的柱子。两边界之间的距离就是这根柱子能展开的最大宽度。但为每根柱子都做一次双向扫描，时间复杂度是 O(n²)。这道困难题的核心挑战就是：怎样在一次线性扫描中，把所有柱子的左右边界同时找齐？

单调栈推进，看矩形如何框出。

标准样例 [2, 1, 5, 6, 2, 3] 的最大面积是 10。点击“下一步”，观察每根柱子入栈时的单调性维护，以及遇到更矮柱子时触发出栈、结算局部矩形的过程。

用递增栈，在弹栈时结算两端。

1. 01

   栈里只存下标，不存高度

   高度随时可以通过 heights[idx] 取到；但如果不存下标，出栈时就无法知道这根柱子在横坐标上的确切位置，进而无法计算矩形宽度。

2. 02

   栈内严格保持高度单调递增

   当扫描到的新柱子比栈顶更矮时，栈顶柱子向右延伸的边界就找到了（就是当前位置 i）。它不能再往右扩展，必须立即弹出结算。

3. 03

   弹出后的新栈顶，就是左边界

   因为栈里存的是单调递增序列，栈顶被弹出后，新的栈顶元素就是它左侧第一个比它更矮的柱子。左右边界瞬间由两端闭环锁死。

虚拟哨兵与弹栈宽度计算。

这段代码来自仓库解法。在数组末尾引入一个高度为 0 的虚拟哨兵，能干净利接地在循环末尾把栈内残留的所有柱子全部逼出并完成结算，无需在循环后重写一段清栈代码。

int largestRectangleArea(int *heights, int heightsSize) {
    TOP = -1;
    int max = 0;
    for (int i = 0; i <= heightsSize; i++) {
        /* i == heightsSize 时用 0 作为虚拟哨兵，强制弹出栈内剩余元素 */
        int curHeight = (i == heightsSize) ? 0 : heights[i];

        while (TOP != -1 && curHeight < heights[stack[TOP]]) {
            int idx = stack[TOP];
            pop();

            int right = i;
            int height = heights[idx];
            int width;

            /* 若弹栈后栈空，说明左边没有更矮的柱子，可一路延伸到 0 */
            if (TOP == -1) {
                width = right;
            } else {
                width = right - stack[TOP] - 1;
            }

            int area = height * width;
            if (area > max) {
                max = area;
            }
        }

        if (i < heightsSize) {
            push(i);
        }
    }
    return max;
}

仓库实现使用固定大小静态数组 stack[MAXN] 模拟栈，TOP 初始为 -1，避免动态内存分配开销。

原复盘里，留下的四个提醒。

这四条真实记录在当时的题目笔记中。单调栈的代码行数不多，但下标与高度的混淆、边界哨兵的处理，往往是容易卡壳的地方。

01 栈里存下标，不存高度

栈里一定要存下标，需要高度时通过 heights[stack[TOP]] 查表。如果存了高度，弹出时就会丢掉位置信息，无法计算宽度。

02 比较时不要拿高度和下标比

写循环条件时容易误写成 curHeight < stack[TOP]。因为 stack[TOP] 是下标，必须用 heights[stack[TOP]] 取出柱子高度再做比较。

03 虚拟哨兵避免修改原数组

在本地开大数组写 heights[heightsSize] = 0 往往能跑，但在判题平台上原数组长度固定，写越界会导致内存错误。用三元运算符 (i == heightsSize) ? 0 : heights[i] 可以安全地获得哨兵。

04 弹栈后栈空与否的宽度计算

弹栈后若栈空，说明左边没有更矮的柱子，宽度就是 right（即下标 i）；若栈非空，宽度是 right - stack[TOP] - 1，千万别漏减 1。

用几种典型形态，检查边界。

让单调性，替我们省下二次扫描。

这道困难题最精妙的地方在于：栈顶元素的左右两端，恰好分别是由“当前即将入栈的更矮柱子”与“弹出后的新栈顶”天然界定的。维持单调性的同时，自动完成了两端更矮位置的探测，将原本需要两头查找的 $O(n^2)$ 降到了纯线性的 $O(n)$。

上述复杂度对应仓库中的 C 解法。本页步进演示额外保留了单调栈各步骤快照，以支持前后回看。