柱状图中最大的矩形 - 三种解法与交互式可视化

题目描述 (LC 84)

给定一个整数数组 heights，表示柱状图中各个柱子的高度，每个柱子宽度为 1。返回柱状图中最大矩形的面积。

示例 1：

• 输入：heights = [2,1,5,6,2,3]
• 输出：10
• 最大矩形覆盖高度为 5 和 6 的柱子，高度为 5，宽度为 2。

示例 2：

• 输入：heights = [2,4]
• 输出：4

---

核心思路

高度一定来自数组

最大矩形的高度一定是 heights 数组中的某个值。为什么？

如果我们选一个不在数组中的高度（比如 4），那我们总可以把高度增加到碰到某根柱子的顶端，从而得到更大的矩形。矛盾！

把问题“固定高度”来思考（最关键的换视角）

对每个下标 i，把 heights[i] 当作矩形的最矮高度（矩形高度固定为 heights[i]），那么这个矩形能向左右扩展到哪里？

• 向左扩展：直到遇到第一个严格更小的高度，不能再跨过去
• 向右扩展：同理，直到遇到第一个严格更小的高度

所以每个 i 的答案都可以写成：

• left[i] = i 左侧第一个 < heights[i] 的下标（没有则 -1）
• right[i] = i 右侧第一个 < heights[i] 的下标（没有则 n）
• width = right[i] - left[i] - 1
• area = heights[i] * width

每根柱子需要知道什么

对于下标 i 处高度为 h = heights[i] 的柱子，如果以它作为矩形的高度，我们需要：

1. 左边界：左边第一个比 h 小的柱子的下标（如果没有则为 -1）
2. 右边界：右边第一个比 h 小的柱子的下标（如果没有则为 n）

然后：宽度 = right[i] - left[i] - 1，面积 = h × 宽度

为什么是”第一个更小”？

如果我们找的不是最近的更小柱子，而是更远的，矩形就会越界，包含不该包含的区域。

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

对于下标 2 的柱子（高度 5）：
- 左边界：下标 1（高度 1 < 5）  ✓
- 右边界：下标 4（高度 2 < 5）  ✓
- 宽度 = 4 - 1 - 1 = 2
- 面积 = 5 × 2 = 10

---

解法一：三次遍历（最直观）

最直接的思路：用单调栈分别求左右边界。

栈里存什么？保持什么不变量？

• 栈里存下标（不是高度），方便算宽度
• 从栈底到栈顶，对应的高度是严格递增的：

heights[stack[0]] < heights[stack[1]] < ... < heights[stack[top]]

这意味着：栈顶永远是“目前为止，最右边的、且高度尽量小的候选柱子”。当我们遇到更矮（或等高）柱子时，栈里更高的柱子就无法再向右延伸了，它们的边界信息会被确定。

算法步骤

1. 第一遍（从左到右）：对每个柱子，找 left[i] = 左边第一个更小柱子的下标
2. 第二遍（从右到左）：对每个柱子，找 right[i] = 右边第一个更小柱子的下标
3. 第三遍：计算每根柱子对应的矩形面积，取最大值

为什么单调栈有效

单调递增栈可以高效地找到”下一个更小元素”：

• 遇到当前柱子 heights[i] 时，先把所有 ≥ heights[i] 的下标弹出
  • 因为这些柱子“更高或等高”，它们不可能成为 i 的“第一个更小”
  • 同时也避免等高柱子重复计数（后面会专门解释）
• 弹完后，栈顶（如果存在）就是 i 左侧第一个 < heights[i] 的下标，也就是 left[i]

JavaPythonJavaScript

Loading...

执行过程

heights = [2, 1, 5, 6, 2, 3]

第一遍（找 left[]）：
i=0: 栈空 → left[0]=-1，入栈 0
i=1: heights[0]=2 > 1 → 弹出 0，栈空 → left[1]=-1，入栈 1
i=2: heights[1]=1 < 5 → left[2]=1，入栈 2
i=3: heights[2]=5 < 6 → left[3]=2，入栈 3
i=4: 弹出 3,2（都 >= 2）→ left[4]=1，入栈 4
i=5: heights[4]=2 < 3 → left[5]=4，入栈 5

left = [-1, -1, 1, 2, 1, 4]

第二遍（找 right[]）：
i=5: 栈空 → right[5]=6，入栈 5
i=4: heights[5]=3 > 2 → 弹出 5，栈空 → right[4]=6，入栈 4
i=3: heights[4]=2 < 6 → right[3]=4，入栈 3
i=2: heights[3]=6 > 5 → 弹出 3，heights[4]=2 < 5 → right[2]=4，入栈 2
i=1: 弹出 2,4 → right[1]=6，入栈 1
i=0: heights[1]=1 < 2 → right[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

---

解法二：两次遍历（优化）

这一版的目标：在从左到右的一次扫描中，同时填出 left[] 和 right[]（然后第二遍只做面积计算）。

关键发现：为什么“弹出时就知道 right”？

当我们从左到右扫描到 i（当前高度 h = heights[i]）时：

• 如果栈顶 j 满足 heights[j] ≥ h，那就要弹出 j
• 一旦弹出 j，说明我们第一次在 j 的右边遇到一个高度 ≤ heights[j] 的柱子
• 因为在 j 入栈到现在这段区间里，栈一直是递增的：只要右侧出现更小/等高，j 就不可能跨过 i 再延伸

因此可以直接写：right[j] = i（i 就是 j 的右边界）。

而对当前 i 来说：

• 在弹出所有 ≥ h 后，栈顶（如果存在）就是 left[i]（左侧第一个更小）
• 再把 i 入栈，继续扫描

等高怎么处理？为什么用 >= 而不是 >？

这里我们用的是 while heights[stack.top] >= heights[i]。

• 好处：等高柱子会“合并”成最右边那个作为代表，避免重复计算同一高度的最大宽度
• 直觉：对于一段等高柱子 [k ... t]，以最左的柱子做高度和以最右的柱子做高度，最终最大面积会被其中一个覆盖；用 >= 能让边界更一致，写法也更稳定

注意：这会让 right[] 变成“第一个 ≤ 当前高度的位置”（而不是严格 <）。但面积计算依然正确，因为我们始终保证“代表柱子”能拿到那段等高区域的最大可扩展宽度。

JavaPythonJavaScript

Loading...

等高区间 [k ... t] 的覆盖示例

heights = [1, 3, 3, 3, 2]
           0  1  2  3  4

• 对等高区间 [1..3]（高度 3），算法在扫描到下标 4（高度 2）时会连续弹出 3、2、1：
  • 最右侧的等高柱子 i=3 会作为“代表”，得到 left=0、right=4，面积 3 × (4-0-1) = 9
  • 之前的等高柱子（i=1,2）在遇到等高/更小高度时已被弹出并写入较近的右边界，但它们不是最大面积的承担者
• 结果最大矩形面积为 9，覆盖整个等高段 [1..3]，这验证了用 >= 的写法可以稳健地处理等高区间。

用同一个例子走一遍（只看关键 pop）

heights = [2, 1, 5, 6, 2, 3]
初始化：left = [-1...], right = [n...], stack = []

i=0, h=2: stack 空 → left[0]=-1，push 0
i=1, h=1: heights[0]=2 >= 1 → pop 0，设置 right[0]=1
          stack 空 → left[1]=-1，push 1
i=2, h=5: heights[1]=1 < 5 → left[2]=1，push 2
i=3, h=6: heights[2]=5 < 6 → left[3]=2，push 3
i=4, h=2: heights[3]=6 >= 2 → pop 3，right[3]=4
          heights[2]=5 >= 2 → pop 2，right[2]=4
          heights[1]=1 < 2 → left[4]=1，push 4
i=5, h=3: heights[4]=2 < 3 → left[5]=4，push 5

此时：
left  = [-1, -1, 1, 2, 1, 4]
right = [ 1,  6, 4, 4, 6, 6]  // 没被 pop 的右边界默认 n=6

---

解法三：一次遍历（最优）

终极优化

上面两种做法本质上都是：

• 先把 left[]/right[] 求出来
• 再统一算面积

但其实没必要存完整数组：在弹出某根柱子的时候，它的“可扩展宽度”已经完全确定了，可以立刻算面积。

可以！弹出元素时：

• 右边界：当前下标（触发弹出的元素）
• 左边界：栈中下一个元素！

这一版最重要的不变量

依然维护一个“高度递增”的栈（存下标）。

当扫描到 i（高度 h）并触发弹出 p 时：

• right = i：因为 h <= heights[p]，i 是 p 右侧第一个让它“停下”的位置
• left = stack.peek()（弹出后新的栈顶）：因为它是 p 左侧最近且严格更小的柱子

于是 p 的最大矩形面积就是：

area(p) = heights[p] * (right - left - 1)

使用哨兵

为了简化边界处理：

• 在栈底放 -1 作为左哨兵 — 处理”左边没有更小柱子”的情况
• 在 heights 末尾加 -1 作为右哨兵 — 确保所有元素都被弹出

原数组：[2, 1, 5, 6, 2, 3]
加哨兵：栈初始为 [-1]，处理 heights + [-1]

JavaPythonJavaScript

Loading...

用例子理解“一次遍历”的 pop（核心就在 i=4 这一步）

heights = [2, 1, 5, 6, 2, 3]，末尾加 -1
stack 初始 [-1]

i=0, h=2: push 0        stack [-1,0]
i=1, h=1: pop 0:
          right=1, left=-1 → area = 2 * (1-(-1)-1)=2
          push 1         stack [-1,1]
i=2, h=5: push 2        stack [-1,1,2]
i=3, h=6: push 3        stack [-1,1,2,3]

i=4, h=2: 触发连续 pop（因为 6>=2, 5>=2）：
  pop 3 (height=6):
    right=4, left=2 → area = 6 * (4-2-1)=6
  pop 2 (height=5):
    right=4, left=1 → area = 5 * (4-1-1)=10  ← 最大矩形在这里算出来
  然后 push 4           stack [-1,1,4]

最后扫到末尾的 -1 时，会把栈里剩下的柱子全部 pop 掉，相当于“统一清算”。

栈底的哨兵 -1 确保我们总有一个有效的”左边界”（意味着柱子可以一直延伸到最左边）。

---

交互式可视化

尝试不同的解法，看看每种方法是如何一步步工作的：

Initializing...

关键观察

1. 三次遍历：最容易理解，分别计算 left[] 和 right[]
2. 两次遍历：发现弹出时就能得到右边界
3. 一次遍历：用哨兵实现弹出时即时计算面积

---

复杂度分析

解法	时间	空间
三次遍历	O(n)	O(n)
两次遍历	O(n)	O(n)
一次遍历	O(n)	O(n)

三种解法的渐进复杂度相同，因为每个元素最多入栈出栈一次。一次遍历的常数稍小，因为遍历次数更少。

空间明细

• 栈：最坏情况 O(n)（递增高度）
• 数组（left、right）：三次遍历和两次遍历需要 O(n)
• 一次遍历不需要单独的数组（略有优势）

---

相关题目

题目	难度	核心思路
LC 85: 最大矩形	困难	对每一行应用 LC 84
LC 42: 接雨水	困难	类似的单调栈模式
LC 739: 每日温度	中等	下一个更大元素
LC 496: 下一个更大元素 I	简单	基础单调栈

模式识别

看到这些关键词，想到单调栈：

• “第一个/下一个更大/更小元素”
• “柱状图中最大矩形”
• “延伸到更小/更大为止的宽度”
• “带边界的面积计算”

---

总结

方法	遍历次数	核心技巧
三次遍历	3	分别计算左右边界
两次遍历	2	弹出时立即得到右边界
一次遍历	1	哨兵 + 弹出时计算

从三次遍历到一次遍历的演进，展示了如何通过识别每个时刻可用的信息来逐步优化。一次遍历的解法很优雅，但更难推导——先理解三次遍历的解法会让优化路径更清晰。

掌握这道题，你就有了所有柱状图相关面试题的坚实基础！