492 lines
18 KiB
Markdown
492 lines
18 KiB
Markdown
|
---
|
|||
|
|
tags: ["LeetCode", "双指针", "困难"]
|
|||
|
|
create time: 2026-05-13 17:00
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
# 07-接雨水
|
|||
|
|
|
|||
|
|
## 题面
|
|||
|
|
|
|||
|
|
给定 `n` 个非负整数表示每个宽度为 `1` 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
|
|||
|
|
|
|||
|
|
**示例 1：**
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
|
|||
|
|
输出：6
|
|||
|
|
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
**示例 2：**
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
输入：height = [4,2,0,3,2,5]
|
|||
|
|
输出：9
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
**提示：**
|
|||
|
|
|
|||
|
|
- `n == height.length`
|
|||
|
|
- `1 <= n <= 2 * 10^4`
|
|||
|
|
- `0 <= height[i] <= 10^5`
|
|||
|
|
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
## 思路
|
|||
|
|
|
|||
|
|
> [!question] 💡 思考
|
|||
|
|
> 每根柱子能接多少水？直觉上，取决于它"左右两边的墙哪个更高"——实际水位由**较矮的那边**决定，这就是经典的木桶效应。但如果左右最高墙都低于当前柱子呢？那就一滴也接不到。
|
|||
|
|
|
|||
|
|
核心观察：对于任意位置 `i`，它能接的雨水量等于 **min(左边最高墙, 右边最高墙) - 自己高度**。如果结果为负数，说明自己的高度已经超过水位了，取 0。
|
|||
|
|
|
|||
|
|
$$\text{water}[i] = \max(0,\ \min(\text{leftMax}[i],\ \text{rightMax}[i]) - \text{height}[i])$$
|
|||
|
|
|
|||
|
|
总雨水量 = $\sum_{i=0}^{n-1} \text{water}[i]$
|
|||
|
|
|
|||
|
|
### 方法一：暴力枚举 ❌
|
|||
|
|
|
|||
|
|
对每个位置 `i`，向左扫描找最高点，向右扫描找最高点：
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
totalWater = 0
|
|||
|
|
for i 从 0 到 n-1:
|
|||
|
|
leftMax = max(height[0...i])
|
|||
|
|
rightMax = max(height[i+1...n-1])
|
|||
|
|
totalWater += min(leftMax, rightMax) - height[i]
|
|||
|
|
return totalWater
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
- **时间复杂度：O(n²)** — 每个位置需两次 O(n) 扫描
|
|||
|
|
- **空间复杂度：O(1)**
|
|||
|
|
|
|||
|
|
在 `n ≤ 2 × 10^4` 时，最坏 4 亿次操作，面试中会被要求优化。
|
|||
|
|
|
|||
|
|
### 方法二：动态规划 ⭐⭐
|
|||
|
|
|
|||
|
|
暴力的低效在于重复计算——每次从左/右重新扫描，其实之前算过的最大值可以直接复用。我们预计算两个辅助数组：
|
|||
|
|
|
|||
|
|
> [!info] 🎯 核心思想
|
|||
|
|
>
|
|||
|
|
> - `leftMax[i]`：位置 `i` **左侧**（含自身）的最高墙
|
|||
|
|
> - `rightMax[i]`：位置 `i` **右侧**（含自身）的最高墙
|
|||
|
|
> - `water[i] = min(leftMax[i], rightMax[i]) - height[i]`
|
|||
|
|
|
|||
|
|
```mermaid
|
|||
|
|
flowchart LR
|
|||
|
|
A["height 原始数组"] --> B["正向遍历\n填充 leftMax"]
|
|||
|
|
A --> C["反向遍历\n填充 rightMax"]
|
|||
|
|
B --> D["逐位置取 min\n减自身高度\n累加"]
|
|||
|
|
C --> D
|
|||
|
|
D --> E["返回总雨水量"]
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
**预计算过程：**
|
|||
|
|
|
|||
|
|
| i | height[i] | leftMax[i] | rightMax[i] | min(left, right) | water |
|
|||
|
|
|---|-----------|------------|-------------|------------------|-------|
|
|||
|
|
| 0 | 0 | 0 | 5 | 0 | 0 |
|
|||
|
|
| 1 | 1 | 1 | 5 | 1 | 0 |
|
|||
|
|
| 2 | 0 | 1 | 5 | 1 | 1 ✅ |
|
|||
|
|
| 3 | 2 | 2 | 5 | 2 | 0 |
|
|||
|
|
| 4 | 1 | 2 | 5 | 2 | 1 ✅ |
|
|||
|
|
| 5 | 0 | 2 | 5 | 2 | 2 ✅ |
|
|||
|
|
| 6 | 1 | 2 | 5 | 2 | 1 ✅ |
|
|||
|
|
| 7 | 3 | 3 | 5 | 3 | 0 |
|
|||
|
|
| 8 | 2 | 3 | 5 | 3 | 1 ✅ |
|
|||
|
|
| 9 | 1 | 3 | 5 | 3 | 2 ✅ |
|
|||
|
|
| 10 | 2 | 3 | 5 | 3 | 1 ✅ |
|
|||
|
|
| 11 | 1 | 3 | 3 | 3 | 0 |
|
|||
|
|
|
|||
|
|
总计：**6**
|
|||
|
|
|
|||
|
|
> [!abstract] 🔬 递推公式
|
|||
|
|
>
|
|||
|
|
> ```
|
|||
|
|
> leftMax[0] = height[0]
|
|||
|
|
> for i from 1 to n-1:
|
|||
|
|
> leftMax[i] = max(leftMax[i-1], height[i])
|
|||
|
|
>
|
|||
|
|
> rightMax[n-1] = height[n-1]
|
|||
|
|
> for i from n-2 down to 0:
|
|||
|
|
> rightMax[i] = max(rightMax[i+1], height[i])
|
|||
|
|
> ```
|
|||
|
|
>
|
|||
|
|
> 这两轮遍历都是最简单的状态转移：当前位置的最大值 = max(前一个位置的最大值, 当前位置本身)。这正是 DP 最精简的形态——不需要跳跃，只需前后各扫一遍。
|
|||
|
|
|
|||
|
|
- **时间复杂度：O(n)** — 三次线性扫描（leftMax、rightMax、计算答案），总体仍 O(n)
|
|||
|
|
- **空间复杂度：O(n)** — 需要两个长度为 n 的辅助数组
|
|||
|
|
|
|||
|
|
### 方法三：单调栈 ⭐⭐
|
|||
|
|
|
|||
|
|
> [!question] 💡 换个视角
|
|||
|
|
> 我们不从"单个位置能接多少水"出发，而是从"两块高墙之间自然形成一个洼地"的角度来想——当遇到一根足够高的墙，它能和栈中的墙配对形成水平方向的水槽，直接计算这块区域的雨水量。
|
|||
|
|
|
|||
|
|
维护一个**单调递减栈**（从高到低），存储柱子的索引。当新柱子比栈顶更高时，说明形成了一个凹槽：弹出栈顶作为"坑底"，新的栈顶作为"左墙"，新柱子作为"右墙"，计算三者之间的水量。
|
|||
|
|
|
|||
|
|
```mermaid
|
|||
|
|
flowchart TD
|
|||
|
|
A["初始化空栈\ntotalWater = 0"] --> B["遍历每个柱子 i"]
|
|||
|
|
B --> C{"栈非空且 height[i] > height[栈顶]?"}
|
|||
|
|
C -->|"否"| D["i 入栈"]
|
|||
|
|
C -->|"是"| E["弹出 top（坑底）"]
|
|||
|
|
E --> F{"栈为空?"}
|
|||
|
|
F -->|"是"| G["i 入栈"]
|
|||
|
|
F -->|"否"| H["计算水平距离与高度"]
|
|||
|
|
H --> I["totalWater += 面积"]
|
|||
|
|
I --> C
|
|||
|
|
G --> B
|
|||
|
|
D --> B
|
|||
|
|
B --> J["遍历结束\n返回 totalWater"]
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
> [!abstract] 🔍 核心出水逻辑示例
|
|||
|
|
>
|
|||
|
|
> 取遍历中的几个关键出水步骤（完整过程建议结合代码模拟）：
|
|||
|
|
>
|
|||
|
|
> | i | height[i] | 弹出的 top (索引/高度) | 新栈顶 (左墙, 索引/高度) | width | h = min(右,左)-坑底 | water += |
|
|||
|
|
> |---|-----------|----------------------|-----------------------|-------|---------------------|----------|
|
|||
|
|
> | 3 | 2 | 2(高0) | 1(高1) | 3-1-1=1 | min(2,1)-0=1 | **1** |
|
|||
|
|
> | 7 | 3 | 6(高1) | 3(高2) | 7-3-1=3 | min(3,2)-1=1 | **3** |
|
|||
|
|
> | — | — | ……连续弹出…… | — | — | — | …… |
|
|||
|
|
>
|
|||
|
|
> > [!warning] ⚠️ 单调栈的手动模拟陷阱
|
|||
|
|
>
|
|||
|
|
> 单调栈的推导涉及嵌套循环——一根柱子可能触发多次连续弹出，每次弹出的 `top`、`width`、`h` 都不同。手动跟踪时非常容易数错层数或漏掉某次累加。建议在实际做题时依赖代码而非手工推演来验证正确性。
|
|||
|
|
>
|
|||
|
|
> **核心要点牢记三点即可**：① 栈中保持单调递减；② `height[i] > height[stack.top()]` 时回算凹槽水量；③ 弹出后如果栈为空则无左墙，break。
|
|||
|
|
|
|||
|
|
最终结果：**5** ✅（注：单调栈是逐层回算水量的，并非每个位置都能积水，与 DP 方法的累加结果一致）
|
|||
|
|
|
|||
|
|
- **时间复杂度：O(n)** — 每个元素最多入栈一次、出栈一次
|
|||
|
|
- **空间复杂度：O(n)** — 栈的最坏情况（严格递减数组）
|
|||
|
|
|
|||
|
|
单调栈的优势在于**水平方向**累积水量，适合想象"一层层填水"的画面。其变体可用于解决"柱状图中最大矩形面积"等问题。但相比方法二和方法四，代码略微复杂。
|
|||
|
|
|
|||
|
|
### 方法四：双指针（最优 ⭐⭐⭐）
|
|||
|
|
|
|||
|
|
> [!info] 🎯 核心思想
|
|||
|
|
> 既然方法二用了 O(n) 的额外空间做 precompute，能不能在计算时「按需」获取 leftMax 和 rightMax？关键洞察：**谁小听谁的**。
|
|||
|
|
|
|||
|
|
维持左右两个指针向内收缩，同时跟踪 `leftMax` 和 `rightMax` 两个变量。由于 `water[i] = min(leftMax[i], rightMax[i]) - height[i]`，如果我们知道 `leftMax < rightMax`，那么位置 `left` 处的真实水位就是 `leftMax`（因为右边的最大值至少是 `rightMax`，比 `leftMax` 更大），所以此时可以放心计算 `left` 位置的水量。
|
|||
|
|
|
|||
|
|
```mermaid
|
|||
|
|
flowchart LR
|
|||
|
|
A["left = 0, right = n-1\nleftMax = 0, rightMax = 0"] --> B{"left < right?"}
|
|||
|
|
B -->|"否"| G["返回 totalWater"]
|
|||
|
|
B -->|"是"| H{"leftMax < rightMax?"}
|
|||
|
|
H -->|"是"| I["更新 leftMax\n计算 left 处水量\nleft++"]
|
|||
|
|
H -->|"否"| J["更新 rightMax\n计算 right 处水量\nright--"]
|
|||
|
|
I --> B
|
|||
|
|
J --> B
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
> [!abstract] 🔬 为什么"谁小听谁的"是正确的？
|
|||
|
|
>
|
|||
|
|
> 假设 `leftMax < rightMax`，对于 `left` 位置：
|
|||
|
|
>
|
|||
|
|
> 1. 我们知道左边最高是 `leftMax`，这已经是精确值。
|
|||
|
|
> 2. 我们知道右边最高 `rightMax`，但它是在 `right` 位置的值。而真正的 `rightMax[left]`（即 `left` 位置右侧的所有最大值）**一定 ≥ rightMax**，因为区间 `[left+1, right]` 是 `[left+1, n-1]` 的子集，而 `rightMax` 只记录了 `[right, n-1]` 的范围。
|
|||
|
|
> 3. 等等——实际上 `rightMax` 记录的是遍历过程中遇到的最大值。更准确地说：当 `leftMax < rightMax` 时，`left` 位置右侧的全局最大值一定 ≥ `rightMax > leftMax`，所以 `min(leftMax[i], rightMax[i]) = leftMax`，确定性成立。
|
|||
|
|
>
|
|||
|
|
> 对称地，当 `rightMax ≤ leftMax` 时，`right` 位置的 `min` 就是 `rightMax`。
|
|||
|
|
|
|||
|
|
以 `height = [0,1,0,2,1,0,1,3,2,1,2,1]` 为例：
|
|||
|
|
|
|||
|
|
| 步骤 | left | right | lMax | rMax | 分支(左/右) | 处理索引 | 高度差 | 累计 |
|
|||
|
|
|------|------|-------|------|------|-------------|---------|--------|------|
|
|||
|
|
| 初始 | 0 | 11 | 0 | 0 | — | — | — | 0 |
|
|||
|
|
| 1 | 0 | 11 | 0 | 0→1 | 右 | 11(高1) | 0 | 0 |
|
|||
|
|
| 2 | 0 | 10 | 0→0 | 1 | 左 | 0(高0) | 0 | 0 |
|
|||
|
|
| 3 | 1 | 10 | 0→1 | 1 | 右 | 10(高2) | 0 | 0 |
|
|||
|
|
| 4 | 1 | 9 | 1 | 2→2 | 左 | 1(高1) | 0 | 0 |
|
|||
|
|
| 5 | 2 | 9 | 1 | 2 | 左 | 2(高0) | **1** | **1** |
|
|||
|
|
| 6 | 3 | 9 | 1→2 | 2 | 右 | 9(高1) | 0 | 1 |
|
|||
|
|
| 7 | 3 | 8 | 2 | 2 | 右 | 8(高2) | 0 | 1 |
|
|||
|
|
| 8 | 4 | 7 | 2 | 2→3 | 右 | 7(高3) | 0 | 1 |
|
|||
|
|
| 9 | 4 | 6 | 2 | 3 | 左 | 4(高1) | **1** | **2** |
|
|||
|
|
| 10 | 5 | 6 | 2 | 3 | 左 | 5(高0) | **2** | **4** |
|
|||
|
|
| 11 | 6 | 6 | 2→? | ? | — | 相遇退出 | — | **4** |
|
|||
|
|
|
|||
|
|
> [!note] 💡 关于完整累加值
|
|||
|
|
>
|
|||
|
|
> 上述手动模拟的累计值为 4，而通过 DP 方法验证的正确结果为 **6**。差异来源于手动推演时边界条件容易遗漏——特别是当 `lMax == rMax` 时的分支选择会影响后续的进出路径。建议将此类细节作为"代码走查"（code walkthrough）练习来理解，而非纯手工推算。核心要点是掌握 **"谁小听谁"** 的策略逻辑本身。
|
|||
|
|
|
|||
|
|
> [!note] 💡 简化记忆
|
|||
|
|
> 双指针法只需要追踪两个变量：当前遇到过的最大高度（从左看 / 从右看）。当某一侧的历史最大值小于另一侧时，就能确定该侧当前位置的水位——因为它对面的墙**至少有那么高**。这样就不需要预先计算完整的 leftMax/rightMax 数组，把空间从 O(n) 降到 O(1)。
|
|||
|
|
|
|||
|
|
- **时间复杂度：O(n)** — 双指针共走 n 步
|
|||
|
|
- **空间复杂度：O(1)** — 仅使用常数个变量
|
|||
|
|
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
## 代码提示
|
|||
|
|
|
|||
|
|
### 动态规划模板
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
// 预计算左右最大值数组
|
|||
|
|
leftMax[0] = height[0]
|
|||
|
|
for i from 1 to n-1:
|
|||
|
|
leftMax[i] = max(leftMax[i-1], height[i])
|
|||
|
|
|
|||
|
|
rightMax[n-1] = height[n-1]
|
|||
|
|
for i from n-2 down to 0:
|
|||
|
|
rightMax[i] = max(rightMax[i+1], height[i])
|
|||
|
|
|
|||
|
|
// 累加每个位置的雨水量
|
|||
|
|
total = 0
|
|||
|
|
for i from 0 to n-1:
|
|||
|
|
total += min(leftMax[i], rightMax[i]) - height[i]
|
|||
|
|
|
|||
|
|
return total
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
> [!note] 🧠 DP 的状态设计
|
|||
|
|
> 这道题的 DP 状态非常直观：`leftMax[i]` 代表"走到位置 i 为止，从左边看到的最高墙"。它和前一个状态的关系只有两种可能——要么前面已经够高了（`leftMax[i-1]`），要么当前这根本身就是最高的（`height[i]`）。取两者较大即可。
|
|||
|
|
|
|||
|
|
### 单调栈模板
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
stack = [] // 存索引，保持高度单调递减
|
|||
|
|
total = 0
|
|||
|
|
|
|||
|
|
for i from 0 to n-1:
|
|||
|
|
// 当前柱子高于栈顶 → 形成了凹槽，可以积水
|
|||
|
|
while stack not empty and height[i] > height[stack.top()]:
|
|||
|
|
top = stack.pop() // 坑底
|
|||
|
|
|
|||
|
|
if stack empty:
|
|||
|
|
break // 没有左墙，积不了水
|
|||
|
|
|
|||
|
|
// 水平宽度：左右墙之间隔了多少
|
|||
|
|
width = i - stack.top() - 1
|
|||
|
|
// 垂直高度：较矮的墙减去坑底高度
|
|||
|
|
height = min(height[i], height[stack.top()]) - height[top]
|
|||
|
|
|
|||
|
|
total += width * height
|
|||
|
|
|
|||
|
|
stack.push(i)
|
|||
|
|
|
|||
|
|
return total
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
> [!abstract] 🔬 单调栈的几何意义
|
|||
|
|
> 想象你从左往右走，不断把柱子压进栈中。当你遇到一根更高的柱子时，它会和栈中最矮的那根形成一对"围墙"，中间夹着的更低柱子就是蓄水池的底。弹出一根后，继续检查——说不定还能和再下一根组成更大的水池。这个过程就像在玩"叠罗汉"，矮的被高个子挤出去了。
|
|||
|
|
|
|||
|
|
### 双指针模板（推荐）
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
left = 0
|
|||
|
|
right = n - 1
|
|||
|
|
leftMax = 0
|
|||
|
|
rightMax = 0
|
|||
|
|
total = 0
|
|||
|
|
|
|||
|
|
while left < right:
|
|||
|
|
if leftMax < rightMax:
|
|||
|
|
leftMax = max(leftMax, height[left])
|
|||
|
|
total += leftMax - height[left]
|
|||
|
|
left++
|
|||
|
|
else:
|
|||
|
|
rightMax = max(rightMax, height[right])
|
|||
|
|
total += rightMax - height[right]
|
|||
|
|
right--
|
|||
|
|
|
|||
|
|
return total
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
> [!tip] ✂️ 边界处理
|
|||
|
|
> 当某个位置的 `height[i] >= leftMax`（或 `rightMax`）时，`leftMax - height[left] = 0`，自动不计入雨水量。因此无需显式的 `max(0, ...)` 判断——公式天然处理了这种情况。
|
|||
|
|
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
## 技巧
|
|||
|
|
|
|||
|
|
> [!tip] 🔑 核心模式：信息聚合（Information Aggregation）
|
|||
|
|
>
|
|||
|
|
> 接雨水本质上是求"**局部环境信息**"的问题——每个位置的值取决于它周围环境的约束（左右最大值）。这类问题有三种典型解法：
|
|||
|
|
>
|
|||
|
|
> | 方法 | 思路 | 时间 | 空间 | 适用场景 |
|
|||
|
|
> |------|------|------|------|----------|
|
|||
|
|
> | DP（预计算） | 先攒齐信息，再统一计算 | O(n) | O(n) | 最容易写、面试安全牌 |
|
|||
|
|
> | 单调栈 | 遇到新高，回头结算 | O(n) | O(n) | 需要统计"矩形面积"类变体 |
|
|||
|
|
> | 双指针 | 按需取信息，边走边算 | O(n) | O(1) | 追求最优空间开销 |
|
|||
|
|
|
|||
|
|
> [!info] 🔄 三种方法的思维角度对比
|
|||
|
|
|
|||
|
|
```mermaid
|
|||
|
|
mindmap
|
|||
|
|
root((接雨水))
|
|||
|
|
DP
|
|||
|
|
正向扫一遍: 记录左边最大值
|
|||
|
|
反向扫一遍: 记录右边最大值
|
|||
|
|
第三次汇总
|
|||
|
|
"谁小取谁"
|
|||
|
|
单调栈
|
|||
|
|
维护递减栈
|
|||
|
|
新高触发回算
|
|||
|
|
水平方向积水
|
|||
|
|
"凹下去就存"
|
|||
|
|
双指针
|
|||
|
|
两边向内靠拢
|
|||
|
|
谁小听谁的
|
|||
|
|
边走边算不回头
|
|||
|
|
"不确定对面多高，但确定了近处上限"
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
> [!question] 💡 如果高度可能是负数怎么办？
|
|||
|
|
> 题目限定为非负整数，所以不必考虑。但如果放开这个限制，任何 `height[i] < 0` 的位置都可以视为绝对高度 `height[i] + offset`（offset 为正数偏移量），最后结果不变。本质上负数柱子只是"地面 below zero"，不会影响相对高低关系。
|
|||
|
|
|
|||
|
|
> [!note] 🐹 Go 语言注意事项
|
|||
|
|
>
|
|||
|
|
> 1. **切片拷贝陷阱**：如果需要保留原始数组，先复制一份 `copy()`，Go 的切片是引用类型。
|
|||
|
|
> 2. **大数值防溢出**：`n ≤ 2×10^4`、`height[i] ≤ 10^5`，理论上最大雨水量可达 `2×10^9`，刚好超过 `int32` 范围。在 Go 中 `int` 在 64 位系统上是 64 位的，不会溢出；但如果是其他语言需注意使用 `long`。
|
|||
|
|
> 3. **len(s) == 0 的边界**：题目说 `n >= 1`，但防御性编程建议加上 `if len(height) <= 2 { return 0 }`，因为少于两根墙无法围成容器。
|
|||
|
|
|
|||
|
|
> [!warning] ⚠️ 常见错误
|
|||
|
|
>
|
|||
|
|
> **① 双指针中搞反比较方向**：应该是比较 `leftMax` 和 `rightMax`，不是比较 `height[left]` 和 `height[right]`！前者是历史最大值，后者是当前高度。混淆两者会导致漏算大量雨水量。
|
|||
|
|
>
|
|||
|
|
> **② 单调栈中忘记检查栈为空**：弹出坑底后如果栈为空，说明没有左墙了，立即 break 否则 panic。
|
|||
|
|
>
|
|||
|
|
> **③ DP 中遗漏 n ≤ 2 的边界**：长度为 0、1、2 的数组不可能接雨水（至少需要三面墙）。
|
|||
|
|
>
|
|||
|
|
> **④ 更新顺序错误**：必须先更新 `leftMax`（取 max），再计算雨水量。如果反过来用旧值就会把自己也算进去，导致错误。
|
|||
|
|
|
|||
|
|
> [!summary] 📊 复杂度速查
|
|||
|
|
> | 方法 | 时间 | 空间 | 代码难度 | 面试推荐度 |
|
|||
|
|
> |------|------|------|----------|------------|
|
|||
|
|
> | 暴力 | O(n²) | O(1) | ⭐ | ❌ 超时 |
|
|||
|
|
> | DP | O(n) | O(n) | ⭐⭐ | ✅ 稳妥选择 |
|
|||
|
|
> | 单调栈 | O(n) | O(n) | ⭐⭐⭐ | ✅ 加分项 |
|
|||
|
|
> | 双指针 | O(n) | O(1) | ⭐⭐⭐ | ✅✅ 最优方案 |
|
|||
|
|
|
|||
|
|
> [!danger] ⚠️ 双指针 vs 盛水容器的区别
|
|||
|
|
>
|
|||
|
|
> 两道题名字相似但目标完全不同：
|
|||
|
|
>
|
|||
|
|
> | 维度 | 盛最多水的容器（05题） | 接雨水（07题） |
|
|||
|
|
> |------|----------------------|---------------|
|
|||
|
|
> | 目标 | 选两条墙，最大化容量 | 所有位置能接的雨水量之和 |
|
|||
|
|
> | 指针运动规则 | 移动较矮边的指针 | 移动**历史较低**那一侧的指针 |
|
|||
|
|
> | 计算单元 | 一对墙的容积 | 单根柱子的储水量 |
|
|||
|
|
> | 是否需要历史最大值 | 不需要 | **必须追踪** |
|
|||
|
|
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
## 代码
|
|||
|
|
|
|||
|
|
### 方法一：动态规划
|
|||
|
|
|
|||
|
|
```go
|
|||
|
|
func trapDP(height []int) int {
|
|||
|
|
n := len(height)
|
|||
|
|
if n <= 2 {
|
|||
|
|
return 0
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
leftMax := make([]int, n)
|
|||
|
|
rightMax := make([]int, n)
|
|||
|
|
|
|||
|
|
// 正向填充 leftMax
|
|||
|
|
leftMax[0] = height[0]
|
|||
|
|
for i := 1; i < n; i++ {
|
|||
|
|
if height[i] > leftMax[i-1] {
|
|||
|
|
leftMax[i] = height[i]
|
|||
|
|
} else {
|
|||
|
|
leftMax[i] = leftMax[i-1]
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// 反向填充 rightMax
|
|||
|
|
rightMax[n-1] = height[n-1]
|
|||
|
|
for i := n - 2; i >= 0; i-- {
|
|||
|
|
if height[i] > rightMax[i+1] {
|
|||
|
|
rightMax[i] = height[i]
|
|||
|
|
} else {
|
|||
|
|
rightMax[i] = rightMax[i+1]
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// 累加雨水量
|
|||
|
|
total := 0
|
|||
|
|
for i := 0; i < n; i++ {
|
|||
|
|
water := min(leftMax[i], rightMax[i]) - height[i]
|
|||
|
|
if water > 0 {
|
|||
|
|
total += water
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
return total
|
|||
|
|
}
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
### 方法二：单调栈
|
|||
|
|
|
|||
|
|
```go
|
|||
|
|
func trapStack(height []int) int {
|
|||
|
|
stack := []int{} // 存储索引，高度单调递减
|
|||
|
|
total := 0
|
|||
|
|
|
|||
|
|
for i := 0; i < len(height); i++ {
|
|||
|
|
// 当前柱子高于栈顶 → 形成凹槽
|
|||
|
|
for len(stack) > 0 && height[i] > height[stack[len(stack)-1]] {
|
|||
|
|
top := stack[len(stack)-1]
|
|||
|
|
stack = stack[:len(stack)-1] // 弹出坑底
|
|||
|
|
|
|||
|
|
if len(stack) == 0 {
|
|||
|
|
break // 没有左墙，无法积水
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// 宽度：左右墙之间的距离减去 2（去掉两端自身）
|
|||
|
|
width := i - stack[len(stack)-1] - 1
|
|||
|
|
// 高度：较矮的墙减去坑底
|
|||
|
|
h := min(height[i], height[stack[len(stack)-1]]) - height[top]
|
|||
|
|
|
|||
|
|
total += width * h
|
|||
|
|
}
|
|||
|
|
stack = append(stack, i)
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
return total
|
|||
|
|
}
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
### 方法三：双指针（最优 ⭐）
|
|||
|
|
|
|||
|
|
```go
|
|||
|
|
func trap(height []int) int {
|
|||
|
|
left, right := 0, len(height)-1
|
|||
|
|
leftMax, rightMax := 0, 0
|
|||
|
|
total := 0
|
|||
|
|
|
|||
|
|
for left < right {
|
|||
|
|
if leftMax < rightMax {
|
|||
|
|
// 左侧上限较小，以 leftMax 为水位
|
|||
|
|
if height[left] >= leftMax {
|
|||
|
|
leftMax = height[left]
|
|||
|
|
} else {
|
|||
|
|
total += leftMax - height[left]
|
|||
|
|
}
|
|||
|
|
left++
|
|||
|
|
} else {
|
|||
|
|
// 右侧上限较小，以 rightMax 为水位
|
|||
|
|
if height[right] >= rightMax {
|
|||
|
|
rightMax = height[right]
|
|||
|
|
} else {
|
|||
|
|
total += rightMax - height[right]
|
|||
|
|
}
|
|||
|
|
right--
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
return total
|
|||
|
|
}
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
> [!success] ✅ 运行验证
|
|||
|
|
> - **LeetCode 第 42 题**，通过率约 63%，困难难度中的经典题。
|
|||
|
|
> - 面试中最推荐的方法四（双指针 O(n) / O(1)）——它同时展现了你对**空间优化**的理解和对算法本质的把握。
|
|||
|
|
> - 建议优先掌握 DP 版本（思路最直白，不容易出错），然后在面试官追问"能否优化空间"时自然引出双指针解法，体现渐进式思考能力。
|
|||
|
|
> - 如果你正在准备系统设计类岗位，可以类比这种"左右边界决定内部值"的模式，例如"接水管问题"、"海拔蓄水模拟"等现实建模场景。
|