本文概览：本文讲解柱状图中最大的矩形的核心思路：用单调递增栈一次遍历找到每根柱子的左右边界，从 O(n²) 降到 O(n)

一、题目

image-20250724013000001

二、题目分析

1. 题目要求

给定一个非负整数数组 heights，每个元素表示柱状图中该位置柱子的高度，求能勾勒出的最大矩形面积。

例子：heights = [2, 1, 5, 6, 2, 3]

1
2
3
4
5
6
7
8
9
10
11
柱状图示意（每列代表一根柱子，列高 = 高度值）：

         6
      5  6
      5  6
      5  6
      5  6     3
2     5  6  2  3
2  1  5  6  2  3
---------------------
0  1  2  3  4  5      ← 索引

最大矩形是中间的 [5, 6]，高度 5、宽度 2，面积 = 5 × 2 = 10。

2. 怎么才算一个"矩形"？

随便挑一根柱子，比如挑索引 4（高度 2）的柱子来看：

1
2
3
4
0  1  2  3  4  5        ← 索引
2  1  5  6  2  3        ← 高度
            ↑
     当前柱子（索引4）

以这根柱子的高度 2 作为矩形的高，那么这个矩形要往左右扩展，什么情况下这个高度不成立？

左边或右边出现了一根比它矮的柱子，这个高度就不成立了。

因为矩形必须连续，碰到更矮的柱子就撑不过去。

找左右边界：

1
2
3
4
5
6
7
8
0  1  2  3  4  5        ← 索引
2  1  5  6  2  3        ← 高度
   ↑        ↑
 左边界    当前柱子
(索引1)   (索引4)

→ 左边界：高度 1 < 2，矩形往左扩到这就停
→ 右边界：右边没有比 2 更矮的，扩到最右边为止

  • 左边界：索引 1（高度 1，是第一根比 2 矮的柱子）

  • 右边界：没有比它更矮的，所以到最右边为止

3. 面积公式怎么算？

矩形能覆盖的柱子是 [5, 6, 2, 3]，宽度肉眼可见是 4。但代码里怎么算？

技巧：右边界没有时，自己在数组末尾补一根高度为 0 的"虚拟柱子"。

1
2
3
4
5
0  1  2  3  4  5        ← 索引
2  1  5  6  2  3        ← 原数组
2  1  5  6  2  3  0     ← 末尾补一个 0
                  ↑
         虚拟柱子（索引6）

现在右边界就是索引 6，左边界是索引 1，宽度公式：

1
2
3
4
5
6
width = right - left - 1
      = 6 - 1 - 1
      = 4
area  = height * width
      = 2 * 4
      = 8

公式记忆：左右边界都是"比当前柱子矮的柱子"，所以宽度要把两根边界柱子都排除掉，即 right - left - 1。

4. 暴力思路的问题

最直觉的做法：遍历每根柱子，每次都向左找第一根比它矮的，向右找第一根比它矮的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
for (int i = 0; i < n; i++) {
    // 找左边界
    int left = -1;
    for (int j = i - 1; j >= 0; j--) {
        if (heights[j] < heights[i]) {
            left = j;
            break;
        }
    }
    // 找右边界
    int right = n;
    for (int j = i + 1; j < n; j++) {
        if (heights[j] < heights[i]) {
            right = j;
            break;
        }
    }
    // 计算面积
    maxArea = Math.max(maxArea, heights[i] * (right - left - 1));
}

时间复杂度：O(n²)，每根柱子都要重复扫已经扫过的元素。

5. 核心观察：暴力遍历中的浪费

关键问题：暴力遍历里，找柱子 i 的左边界时，已经把 [0, i-1] 都扫了一遍；但找柱子 i+1 的左边界时，又要重新扫 [0, i]，这些信息完全重复了。

优化思路：能不能只遍历一次，就按顺序找到每根柱子的左右边界？

关键数据结构：单调递增栈。

  • 维护一个高度递增的栈（栈里存索引）

  • 当一根新柱子比栈顶柱子矮时，栈顶柱子的右边界就找到了（就是这根新柱子）

  • 栈顶柱子的左边界就是它在栈里的下一个元素（栈顶出栈后，新的栈顶就是左边界）

和暴力最大的区别：不是实时算每根柱子的面积，而是延时计算——一直憋着算栈顶，到最后一样能算完所有柱子。

三、思路概览

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public int largestRectangleArea(int[] heights) {
    if (heights.length == 0) {
        return 0;
    }
    int maxArea = 0;
    int n = heights.length;
    // 头尾各加一个 0 作为哨兵
    int[] newHeight = new int[n + 2];
    System.arraycopy(heights, 0, newHeight, 1, n);
    // 单调递增栈（存索引）
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < n + 2; i++) {
        // 若栈不为空且当前元素小于栈顶元素，则弹出栈顶元素并计算面积
        while (!stack.isEmpty() && newHeight[i] < newHeight[stack.peekLast()]) {
            // 当前值高度
            int height = newHeight[stack.pollLast()];
            // 左边界
            int left = stack.peekLast();
            // 右边界
            int right = i;
            // 宽度
            int width = right - left - 1;
            // 面积
            maxArea = Math.max(maxArea, height * width);
        }
        // 入栈
        stack.addLast(i);
    }
    return maxArea;
}

思路简要说明：

  1. 哨兵数组：在原数组头尾各加一个 0，保证栈内元素最后全部能弹出
  2. 单调递增栈：栈内索引对应的高度从底到顶递增
  3. 左边界：栈顶出栈后，新的栈顶就是它的左边界
  4. 右边界：触发栈顶出栈的当前柱子就是右边界
  5. 面积公式：height * (right - left - 1)
  6. 延时计算：不是实时算每根柱子，而是憋住算栈顶，最后一定能算完全部

四、思路详解

第一步：左右边界到底怎么确定？

回到核心定义：以柱子 i 的高度为矩形的高时，矩形能向左右延伸到哪？

1
2
3
4
5
0  1  2  3  4  5        ← 索引
2  1  5  6  2  3        ← 高度
   ↑        ↑
 左边界    当前柱子 i
（第一根更矮）

  • 左边界：从柱子 i 往左看，第一根比 heights[i] 矮的柱子

  • 右边界：从柱子 i 往右看，第一根比 heights[i] 矮的柱子

矩形的高是 heights[i]，宽度是中间这段（不含边界），所以：

1
2
width = right - left - 1
area  = heights[i] * (right - left - 1)

第二步：为什么是单调递增栈？

问题：怎么一次遍历就把每根柱子的左右边界都找出来？

思考：如果遍历过程中，已经处理过的柱子的高度是递增的，那么对于一根新柱子：

  • 如果新柱子比栈顶高 → 直接入栈，栈顶的右边界还没到

  • 如果新柱子比栈顶矮 → 栈顶柱子的右边界就是这根新柱子！

那左边界呢？

栈顶柱子出栈后，新的栈顶就是它在栈里的下一个元素，这个元素的高度比它矮（因为递增），所以就是它的左边界。

1
2
3
4
5
6
7
8
9
10
11
栈内（高度递增，左边是栈底，右边是栈顶）：

[A]  [B]  [C]
           ↑
     C 是当前要算的柱子

新柱子 D 比 C 矮：
  C 出栈
  C 的左边界 = B（新的栈顶）
  C 的右边界 = D
  area = heights[C] * (D - B - 1)

单调递增栈的本质：栈内每根柱子的左边界，就是它在栈里的前一根柱子；右边界，由后面第一个比它矮的柱子触发。

第三步：为什么要"延时"计算？

暴力思路：遍历到柱子 i 时，立刻算它的面积 → 需要重新扫左右边界 → O(n²)

单调栈思路：遍历到柱子 i 时，不一定是算柱子 i 的面积，而是算栈顶柱子的面积。

为什么这样也能算完所有柱子？

  • 每根柱子入栈一次

  • 每根柱子出栈一次（被某个更矮的柱子触发）

  • 出栈的那一刻，它的左右边界都已确定，立即算面积

所以遍历结束时，所有柱子都必然被算过一次。

第四步：为什么要加哨兵？

问题：如果数组本身就是递增的，比如 [1, 2, 3, 4, 5]，遍历到最后一根时，栈里所有元素都没机会出栈（因为没有更矮的柱子触发它们）。

解决：在数组末尾加一个 0，0 比任何柱子都矮，必然能把栈里所有元素全部弹出。

开头也要加 0：保证第一根柱子也有左边界（栈底的 0 就是它的左边界），同时避免栈空判断。

1
2
3
4
0  2  1  5  6  2  3  0        ← newHeight（头尾各补一个 0）
↑                    ↑
头哨兵              尾哨兵
（索引0）         （索引7）

哨兵的双重作用：

  1. 尾哨兵：保证遍历结束时栈内所有元素都能弹出，确保每根柱子都被算到
  2. 头哨兵：作为第一根柱子的左边界，避免 stack.peekLast() 在栈只有一个元素时出错

第五步：为什么是 O(n)？

看起来有 while 嵌套在 for 里，应该是 O(n²)？

实际上：每个索引最多入栈一次，出栈一次。

  • 外层 for 循环：n + 2 次

  • 内层 while 循环：所有索引总共出栈 n + 2 次

所以总操作次数是 2(n+2)，时间复杂度 **O(n)**。

完整执行过程

以 heights = [2, 1, 5, 6, 2, 3] 为例，加哨兵后 newHeight = [0, 2, 1, 5, 6, 2, 3, 0]（长度 8）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
初始：stack = [], maxArea = 0

i=0, height=0：
  栈空，0 入栈
  stack = [0]

i=1, height=2：
  2 > 0（栈顶），2 入栈
  stack = [0, 1]

i=2, height=1：
  1 < 2（栈顶），弹出 1
    height=2, left=0, right=2, width=2-0-1=1, area=2×1=2
    maxArea = max(0, 2) = 2
  1 > 0（栈顶），1 入栈
  stack = [0, 2]

i=3, height=5：
  5 > 1（栈顶），5 入栈
  stack = [0, 2, 3]

i=4, height=6：
  6 > 5（栈顶），6 入栈
  stack = [0, 2, 3, 4]

i=5, height=2：
  2 < 6（栈顶），弹出 4
    height=6, left=3, right=5, width=5-3-1=1, area=6×1=6
    maxArea = max(2, 6) = 6
  2 < 5（栈顶），弹出 3
    height=5, left=2, right=5, width=5-2-1=2, area=5×2=10
    maxArea = max(6, 10) = 10
  2 > 1（栈顶），2 入栈
  stack = [0, 2, 5]

i=6, height=3：
  3 > 2（栈顶），3 入栈
  stack = [0, 2, 5, 6]

i=7, height=0（尾哨兵）：
  0 < 3（栈顶），弹出 6
    height=3, left=5, right=7, width=7-5-1=1, area=3×1=3
    maxArea = max(10, 3) = 10
  0 < 2（栈顶），弹出 5
    height=2, left=2, right=7, width=7-2-1=4, area=2×4=8
    maxArea = max(10, 8) = 10
  0 < 1（栈顶），弹出 2
    height=1, left=0, right=7, width=7-0-1=6, area=1×6=6
    maxArea = max(10, 6) = 10
  0 = 0（栈顶），不满足 < 条件，停止弹出
  0 入栈
  stack = [0, 7]

遍历结束，maxArea = 10 ✓

关键观察：

  • 最大面积 10 在 i=5 时算出，对应中间的柱子 [5, 6]（高度 5，宽度 2）

  • 尾哨兵 0 在 i=7 时把栈内剩余柱子全部弹出，保证不漏算

  • 最后栈里剩 [0, 7]（两个哨兵），不影响结果

与"接雨水"的对比

维度 接雨水 柱状图中最大的矩形
关注点 凹槽能存多少水 单根柱子能撑多大矩形
单调栈方向 递减栈（找下一个更高） 递增栈（找下一个更矮）
触发条件 新柱子比栈顶高 新柱子比栈顶矮
边界定义 左右更高柱子围成凹槽 左右更矮柱子围成矩形

五、总结

柱状图中最大的矩形的核心思路：

  1. 矩形定义：以柱子 i 的高度为高，左右边界是第一根比它矮的柱子
  2. 面积公式：height * (right - left - 1)
  3. 单调递增栈：栈顶出栈后，新栈顶是左边界；触发出栈的柱子是右边界
  4. 延时计算：遍历到新柱子时算的是栈顶柱子的面积，不是新柱子的
  5. 哨兵技巧：头尾加 0，保证所有柱子都能出栈被算到
  6. **时间复杂度 O(n)**：每个索引最多入栈一次，出栈一次
  7. **空间复杂度 O(n)**：栈最多存储 n+2 个索引

单调栈的适用场景：

  • 找"下一个更大/更小的元素"

  • 需要维护一个单调序列

  • 暴力遍历中有重复的边界查找