84. 柱状图中最大的矩形 — 单调栈解法详解#

class Solution {
    public int largestRectangleInHistogram(int[] heights) {
        // 原始柱子数量
        int n = heights.length;
        // 新数组：在首尾各加一个高度为 0 的哨兵，统一边界处理
        int[] h = new int[n + 2];
        // 左哨兵：保证弹栈后一定还有“左边界”可取
        h[0] = 0;
        // 右哨兵：在遍历末尾强制触发弹栈，结算所有剩余柱子
        h[n + 1] = 0;
        // 把原数组拷贝到 h[1..n]
        for (int i = 0; i < n; i++) h[i + 1] = heights[i];

        // 单调递增栈：存下标，且对应高度从栈底到栈顶递增
        Deque<Integer> stack = new ArrayDeque<>();
        // 记录扫描过程中的最大矩形面积
        int maxArea = 0;

        // 遍历包含哨兵的新数组
        for (int i = 0; i < h.length; i++) {
            // 若当前高度更小，说明栈顶柱子的“右边第一个更矮柱子”已确定为 i
            while (!stack.isEmpty() && h[i] < h[stack.peek()]) {
                // mid：以它作为矩形高度的候选柱子下标
                int mid = stack.pop();
                // left：弹出后新的栈顶，就是 mid 左边第一个更矮柱子的下标
                int left = stack.peek();
                // right：当前遍历位置 i，就是 mid 右边第一个更矮柱子的下标
                int right = i;
                // 可扩展宽度 = (left, right) 开区间长度，不含两端
                int width = right - left - 1;
                // 以 h[mid] 为高时的最大面积
                int area = h[mid] * width;
                // 更新全局最大面积
                maxArea = Math.max(maxArea, area);
            }
            // 当前柱子下标入栈，继续维护递增高度序列
            stack.push(i);
        }

        // 返回最大矩形面积
        return maxArea;
    }
}

i=0  h=0  栈空，直接入栈         stack: [0]
i=1  h=2  2>0，直接入栈          stack: [0,1]
i=2  h=1  1<2，弹出 mid=1
          left=0, right=2
          宽=2-0-1=1, 面积=2×1=2   maxArea=2
          1>0，入栈               stack: [0,2]
i=3  h=5  5>1，入栈               stack: [0,2,3]
i=4  h=6  6>5，入栈               stack: [0,2,3,4]
i=5  h=2  2<6，弹出 mid=4
          left=3, right=5
          宽=5-3-1=1, 面积=6×1=6   maxArea=6
          2<5，弹出 mid=3
          left=2, right=5
          宽=5-2-1=2, 面积=5×2=10  maxArea=10
          2>1，入栈               stack: [0,2,5]
i=6  h=3  3>2，入栈               stack: [0,2,5,6]
i=7  h=0  0<3，弹出 mid=6
          left=5, right=7
          宽=7-5-1=1, 面积=3×1=3   maxArea=10
          0<2，弹出 mid=5
          left=2, right=7
          宽=7-2-1=4, 面积=2×4=8   maxArea=10
          0<1，弹出 mid=2
          left=0, right=7
          宽=7-0-1=6, 面积=1×6=6   maxArea=10
          栈中只剩哨兵 0，结束

最终答案: 10

栈始终保持从底到顶高度递增：

入栈前若违反单调性，先弹出直到满足为止

    栈顶
     |
    [6]  ← h=6
    [5]  ← h=5
    [1]  ← h=1
    [0]  ← h=0 (哨兵)
     底

遇到 h=2：弹出 6、5，再入栈 2
    [2]
    [1]
    [0]