05 单调栈进阶：柱状图中最大矩形

单调栈进阶：柱状图中最大矩形

摘要

本篇是单调栈的进阶专题，聚焦两道经典困难题：LeetCode 84（Largest Rectangle in Histogram）和 LeetCode 85（Maximal Rectangle）。LeetCode 84 要求在柱状图中找到能围成的最大矩形面积，核心是用单调递增栈在弹栈的瞬间计算”以弹出柱子为高度、能向左右延伸的最大宽度”；LeetCode 85 在此基础上，将二维矩阵的每一行视为一个柱状图的底边，逐行累计高度后调用 84 的解法，把二维问题降维为一维。这两道题放在一起是理解”弹栈时结算”思维模式的最佳练习，也是面试中区分”熟练”和”优秀”候选人的分水岭。

---

第 1 章 LeetCode 84：柱状图中最大的矩形

1.1 题目

LeetCode 84 - Largest Rectangle in Histogram（困难）

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1。求在该柱状图中，能够勾勒出来的矩形的最大面积。

输入: heights = [2,1,5,6,2,3]
输出: 10

  6
  █
5 █
█ █
█ █   3
█ █ 2 █
█ █ █ █
2   █ █ █
█ 1 █ █ █ █
0 1 2 3 4 5
heights = [2,1,5,6,2,3]

最大矩形：以 heights[2]=5 和 heights[3]=6 为基础，高度=5，宽度=2，面积=10

1.2 思路推导：从暴力到单调栈

暴力 $O(n^2)$：枚举每对 (i, j)，以 min(heights[i..j]) 为高度，j - i + 1 为宽度，计算面积。

关键观察：矩形的高度一定等于某根柱子的高度（因为矩形的高由最矮的柱子决定）。也就是说，最大矩形一定是”以某根柱子 k 为高度”的矩形：找到从 k 向左能延伸到哪，向右能延伸到哪——具体是找到左边第一根比 heights[k] 矮的柱子的位置 left，以及右边第一根比 heights[k] 矮的柱子的位置 right，面积就是 heights[k] * (right - left - 1)。

这正是”左边第一个更小元素”和”右边第一个更小元素”的问题——单调栈的典型应用！

1.3 两次单调栈法（Left + Right）

第一步：用单调递增栈（从左往右扫描），求每根柱子的左边界（左边第一个比它矮的柱子）。

第二步：用单调递增栈（从右往左扫描），求每根柱子的右边界（右边第一个比它矮的柱子）。

第三步：对每根柱子，面积 = heights[i] * (right[i] - left[i] - 1)，取最大。

public int largestRectangleArea(int[] heights) {
    int n = heights.length;
    int[] left = new int[n];  // left[i] = i 左边第一个比 heights[i] 小的下标（若无则为 -1）
    int[] right = new int[n]; // right[i] = i 右边第一个比 heights[i] 小的下标（若无则为 n）
    
    // 求 left[]：从左往右，单调递增栈
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
            stack.pop();
        }
        left[i] = stack.isEmpty() ? -1 : stack.peek();
        stack.push(i);
    }
    
    // 求 right[]：从右往左，单调递增栈
    stack.clear();
    for (int i = n - 1; i >= 0; i--) {
        while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
            stack.pop();
        }
        right[i] = stack.isEmpty() ? n : stack.peek();
        stack.push(i);
    }
    
    // 计算最大面积
    int maxArea = 0;
    for (int i = 0; i < n; i++) {
        maxArea = Math.max(maxArea, heights[i] * (right[i] - left[i] - 1));
    }
    return maxArea;
}

严格小于还是小于等于？

求左右边界时，条件是 >= heights[i]（找到严格更小的）。如果用 >（找到不小于的），那对相等的高度会找到错误的边界。 例：heights = [3, 3]。若求 left[1]（heights[1]=3），用 > 时弹出 heights[0]=3（因为 3>3 为 false，不弹），left[1]=0，面积 = 3*(2-0-1)=3；正确答案是面积 6。 但实际上，相等高度的问题只要保证左右边界一致即可（不会重复计算）。常见处理方式：左边找”严格小于”，右边找”小于等于”，避免重复。本例中用 >= 来找严格小于的边界是正确的。

手动验证（heights = [2,1,5,6,2,3]）：

left:
i=0, h=2: 栈空, left[0]=-1, 压0 → [0]
i=1, h=1: 1<=2, 弹0; 栈空, left[1]=-1, 压1 → [1]
i=2, h=5: 5>1, left[2]=1, 压2 → [1,2]
i=3, h=6: 6>5, left[3]=2, 压3 → [1,2,3]
i=4, h=2: 6>=2, 弹3; 5>=2, 弹2; 1<2, left[4]=1, 压4 → [1,4]
i=5, h=3: 3>2, left[5]=4, 压5 → [1,4,5]
left = [-1,-1,1,2,1,4]

right（从右往左）:
i=5, h=3: 栈空, right[5]=6, 压5 → [5]
i=4, h=2: 3>=2, 弹5; 栈空, right[4]=6, 压4 → [4]
i=3, h=6: 6>2, right[3]=4, 压3 → [4,3]
i=2, h=5: 6>=5, 弹3; 2<5, right[2]=4, 压2 → [4,2]
i=1, h=1: 5>=1, 弹2; 2>=1, 弹4; 栈空, right[1]=6, 压1 → [1]
i=0, h=2: 1<2, right[0]=1, 压0 → [1,0]
right = [1,6,4,4,6,6]

面积:
i=0: 2*(1-(-1)-1) = 2*1 = 2
i=1: 1*(6-(-1)-1) = 1*6 = 6
i=2: 5*(4-1-1) = 5*2 = 10 ← 最大
i=3: 6*(4-2-1) = 6*1 = 6
i=4: 2*(6-1-1) = 2*4 = 8
i=5: 3*(6-4-1) = 3*1 = 3

maxArea = 10 ✓

复杂度：时间 $O(n)$，空间 $O(n)$。

---

第 2 章 单次遍历：弹栈时结算

2.1 更优雅的一次遍历写法

上面的两次扫描虽然正确，但需要 left[] 和 right[] 两个辅助数组。更优雅的做法是一次遍历，弹栈时同时计算结果。

思路：维护一个单调递增栈（从底到顶高度严格递增）。当遇到比栈顶更小的元素时，弹出栈顶柱子并结算：

• 弹出的柱子 mid，其高度是 heights[mid]
• 右边界：当前下标 i（第一个比 heights[mid] 小的右边柱子）
• 左边界：新的栈顶 stack.peek()（栈中 mid 下面的柱子，保证小于 heights[mid]）
• 宽度：i - stack.peek() - 1

哨兵技巧：在 heights 数组首尾各加一个高度为 0 的哨兵，确保：

• 所有柱子最终都会被弹出（右哨兵 0 比任何柱子都小）
• 左边界计算不会越界（左哨兵 -1 下标始终在栈底）

public int largestRectangleArea(int[] heights) {
    // 在首尾加高度为 0 的哨兵
    int n = heights.length;
    int[] h = new int[n + 2];
    h[0] = 0;
    System.arraycopy(heights, 0, h, 1, n);
    h[n + 1] = 0;
    
    Deque<Integer> stack = new ArrayDeque<>();
    int maxArea = 0;
    
    for (int i = 0; i < h.length; i++) {
        // 当前高度 < 栈顶高度：弹栈并结算
        while (!stack.isEmpty() && h[i] < h[stack.peek()]) {
            int mid = stack.pop(); // 被弹出的柱子
            int left = stack.peek(); // 新栈顶（左边界的前一个）
            // 宽度 = i - left - 1（left 到 i 之间的柱子，不含端点）
            int area = h[mid] * (i - left - 1);
            maxArea = Math.max(maxArea, area);
        }
        stack.push(i);
    }
    
    return maxArea;
}

手动验证（h = [0, 2,1,5,6,2,3, 0]，加入哨兵）：

i=0, h=0: 栈空，压 0 → [0]
i=1, h=2: 2>0，压 1 → [0,1]
i=2, h=1: 
  1<2: 弹 1（h=2）, left=0, area=2*(2-0-1)=2
  1>0: 停止弹
  压 2 → [0,2]
i=3, h=5: 5>1，压 3 → [0,2,3]
i=4, h=6: 6>5，压 4 → [0,2,3,4]
i=5, h=2:
  2<6: 弹 4（h=6）, left=3, area=6*(5-3-1)=6
  2<5: 弹 3（h=5）, left=2, area=5*(5-2-1)=10 ← maxArea!
  2>1: 停止弹
  压 5 → [0,2,5]
i=6, h=3: 3>2，压 6 → [0,2,5,6]
i=7, h=0:
  0<3: 弹 6（h=3）, left=5, area=3*(7-5-1)=3
  0<2: 弹 5（h=2）, left=2, area=2*(7-2-1)=8
  0<1: 弹 2（h=1）, left=0, area=1*(7-0-1)=6
  0=0: 停止弹
  （压 7，但循环结束）

maxArea = 10 ✓

复杂度：时间 $O(n)$，空间 $O(n)$。比两次扫描略简洁，且只需要一个辅助数组（栈），不需要 left[] 和 right[]。

---

第 3 章 LeetCode 85：最大矩形

3.1 题目

LeetCode 85 - Maximal Rectangle（困难）

给定一个仅包含 0 和 1、大小为 rows x cols 的二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

输入:
matrix = [
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
输出: 6（最大矩形是第2-3行、第2-4列的6个1）

3.2 思路：逐行累计高度，每行调用一次 LeetCode 84

关键洞察：最大矩形（只包含 1）的底边一定位于某一行。对于底边位于第 r 行的矩形，每一列的”高度”是从第 r 行向上连续 1 的个数。

将每一行的”高度数组”视为 LeetCode 84 的 heights 输入，就把二维问题转化为了一系列一维问题：

矩阵:          第0行高度: [1,0,1,0,0]
1 0 1 0 0      第1行高度: [2,0,2,1,1]  （第0列从0行累积：1+1=2）
1 0 1 1 1  →   第2行高度: [3,1,3,2,2]
1 1 1 1 1      第3行高度: [4,0,0,3,0]
1 0 0 1 0

对每行的高度数组调用 LeetCode 84，取最大值。
第2行: [3,1,3,2,2] → 最大矩形面积 = ?
  以 h[0]=3 为高: 宽1, 面积3
  以 h[1]=1 为高: 宽5, 面积5
  以 h[2]=3 为高: 宽1... 
  实际上最优是 h[3]=2 或 h[4]=2，宽2，面积4？
  
  让我重新算：
  heights = [3,1,3,2,2]
  使用 84 的算法（带哨兵）：
  ...实际上 LeetCode 85 的例子给出的答案是 6，来自第2-3行：
  
  第2行（0-indexed）高度: [3,1,3,2,2]
  用单调栈算 LeetCode 84: 最大面积 = 6（以 h[2]=3 到 h[4]=2，高度2，宽度3，面积6）

3.3 代码实现

public int maximalRectangle(char[][] matrix) {
    if (matrix == null || matrix.length == 0) return 0;
    
    int rows = matrix.length;
    int cols = matrix[0].length;
    int[] heights = new int[cols]; // 每列的累计高度
    int maxArea = 0;
    
    for (int r = 0; r < rows; r++) {
        // 更新高度数组
        for (int c = 0; c < cols; c++) {
            if (matrix[r][c] == '1') {
                heights[c]++; // 连续 1，高度累加
            } else {
                heights[c] = 0; // 遇到 0，高度重置
            }
        }
        // 对当前行的高度数组调用 LeetCode 84 的解法
        maxArea = Math.max(maxArea, largestRectangleArea(heights));
    }
    
    return maxArea;
}
 
private int largestRectangleArea(int[] heights) {
    int n = heights.length;
    // 加哨兵
    int[] h = new int[n + 2];
    System.arraycopy(heights, 0, h, 1, n);
    // h[0] = 0, h[n+1] = 0（默认值）
    
    Deque<Integer> stack = new ArrayDeque<>();
    int maxArea = 0;
    
    for (int i = 0; i < h.length; i++) {
        while (!stack.isEmpty() && h[i] < h[stack.peek()]) {
            int mid = stack.pop();
            int left = stack.peek();
            maxArea = Math.max(maxArea, h[mid] * (i - left - 1));
        }
        stack.push(i);
    }
    
    return maxArea;
}

手动验证第 2 行（heights = [3,1,3,2,2]，加哨兵后 h = [0,3,1,3,2,2,0]）：

i=0, h=0: 压 0 → [0]
i=1, h=3: 3>0, 压 1 → [0,1]
i=2, h=1:
  1<3: 弹 1（h=3）, left=0, area=3*(2-0-1)=3
  1>0: 停止
  压 2 → [0,2]
i=3, h=3: 3>1, 压 3 → [0,2,3]
i=4, h=2:
  2<3: 弹 3（h=3）, left=2, area=3*(4-2-1)=3
  2>1: 停止
  压 4 → [0,2,4]
i=5, h=2: 2=2, 压 5 → [0,2,4,5]
i=6, h=0:
  0<2: 弹 5（h=2）, left=4, area=2*(6-4-1)=2
  0<2: 弹 4（h=2）, left=2, area=2*(6-2-1)=6 ← maxArea!
  0<1: 弹 2（h=1）, left=0, area=1*(6-0-1)=5
  0=0: 停止

maxArea = 6 ✓

复杂度：时间 $O(rows\times cols)$（每行调用一次 $O(cols)$ 的 84 解法），空间 $O(cols)$。

---

第 4 章 两道题的核心思维提炼

4.1 “弹栈时结算”模式

LeetCode 84 和之前的 739、496、503 有一个关键差异：739/496/503 在弹栈时只需记录”答案下标”（差值），而 84 在弹栈时需要同时用左右两侧信息计算面积。

弹栈时的信息：

• mid = stack.pop()：被弹出的元素（高度 h[mid]）
• left = stack.peek()：弹出后的新栈顶（左边界，h[left] < h[mid]）
• i：触发弹栈的当前下标（右边界，h[i] < h[mid]）

三个量同时可知，面积即可算出。这是单调栈处理”左右边界同时已知”问题的标准范式。

4.2 从 84 出发的延伸题

题目	思路	与 84 的关系
LeetCode 85（最大矩形）	逐行调用 84	直接应用
LeetCode 42（接雨水）	单调递减栈，弹栈时计算水量	同一范式，方向不同
LeetCode 11（Container With Most Water）	双指针（与单调栈无关）	不同问题

84 与 42 的对比

LeetCode 42（接雨水）和 84（柱状图最大矩形）经常被一起讨论，但解题模式不同：

• LeetCode 84：单调递增栈（保持矩形的左侧高于或等于当前高度），弹栈时计算矩形面积
• LeetCode 42：单调递减栈（保持水槽的左侧高于或等于当前高度），弹栈时计算水量

两者都是”弹栈时结算”，但栈的单调方向不同，结算的物理意义不同。

---

下一篇预告

06 单调队列：滑动窗口最大值 将从”单调栈”过渡到”单调队列”。LeetCode 239（Sliding Window Maximum）要求在 $O(n)$ 时间内求出所有大小为 $k$ 的滑动窗口的最大值——用双端队列（Deque）维护窗口内的单调递减序列，是单调队列最经典的实现。理解单调队列后，可以进一步探讨其在 DP 优化（如跳跃游戏系列）中的应用。