277 lines
12 KiB
Markdown
277 lines
12 KiB
Markdown
---
|
||
tags: ["LeetCode", "贪心算法", "数组", "中等"]
|
||
create time: 2026-05-16 14:35
|
||
---
|
||
|
||
# 79-跳跃游戏 II
|
||
|
||
## 题面
|
||
|
||
给定一个长度为 `n` 的 **0 索引**整数数组 `nums`。初始位置在下标 `0`。
|
||
|
||
每个元素 `nums[i]` 表示从索引 `i` 向后跳转的最大长度。换句话说，如果你在索引 `i` 处，你可以跳转到任意 `(i + j)` 处：
|
||
|
||
- `0 <= j <= nums[i]` 且
|
||
- `i + j < n`
|
||
|
||
返回到达 `n - 1` 的**最小跳跃次数**。测试用例保证可以到达 `n - 1`。
|
||
|
||
**示例 1：**
|
||
|
||
```
|
||
输入：nums = [2,3,1,1,4]
|
||
输出：2
|
||
解释：跳到最后一个位置的最小跳跃数是 2。
|
||
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
|
||
```
|
||
|
||
**示例 2：**
|
||
|
||
```
|
||
输入：nums = [2,3,0,1,4]
|
||
输出：2
|
||
```
|
||
|
||
**提示：**
|
||
|
||
- `1 <= nums.length <= 10⁴`
|
||
- `0 <= nums[i] <= 1000`
|
||
- 题目保证可以到达 `n - 1`
|
||
|
||
---
|
||
|
||
## 思路
|
||
|
||
> [!question] 💡 思考
|
||
> 上道题（跳跃游戏 I）只问"能不能到"，我们用一个变量 `maxReach` 就能回答。现在升级了：不仅要判断可达性，还要在多条路径中找到**跳跃次数最少**的那一条。
|
||
>
|
||
> 🤔 如果你站在下标 0，它允许你跳到 [1, 2]，你会怎么做？选哪个位置作为下一步，才能让后续需要的总跳跃次数最少？
|
||
|
||
### 方法一：暴力枚举所有路径 ❌
|
||
|
||
枚举从每个位置出发能跳的所有距离，对每条路径记录跳跃次数，最后取最小值：
|
||
|
||
```
|
||
minJumps(pos):
|
||
if pos >= n-1: return 0
|
||
result = ∞
|
||
for step from 1 to nums[pos]:
|
||
result = min(result, 1 + minJumps(pos + step))
|
||
return result
|
||
```
|
||
|
||
以 `nums = [2,3,1,1,4]` 为例，可能的路径有：
|
||
|
||
| 路径 | 跳跃次数 |
|
||
|------|---------|
|
||
| 0 → 1 → 4 | 2 |
|
||
| 0 → 2 → 3 → 4 | 3 |
|
||
| 0 → 2 → 4 | 2 |
|
||
| 0 → 1 → 2 → ... | ≥ 3 |
|
||
| 0 → 1 → 3 → 4 | 3 |
|
||
|
||
- **时间复杂度：O(n!)** — 在最坏情况下（如全为较大值），分支因子巨大
|
||
- **空间复杂度：O(n)** — 递归栈深度
|
||
|
||
显然不可行。但我们发现：**不需要穷举所有路径**——关键 insight 是，每次跳远范围时，只要在"当前这一步能到的范围内"找到最远能延伸到哪里即可。
|
||
|
||
### 方法二：贪心算法 —— BFS 式逐层推进 ⭐
|
||
|
||
> [!info] 🎯 核心思想
|
||
> 将数组看作一层层的"跳跃区间"。第 1 步能到达的范围是 `[0, nums[0]]`，第 2 步在此基础上向外扩展，依此类推。每一步我们都选择能让边界扩张最多的那个位置，这就是贪心。
|
||
|
||
具体策略引入两个关键变量：
|
||
|
||
| 变量 | 含义 |
|
||
|------|------|
|
||
| `maxReach` | 从任意已访问位置出发，能到达的最远索引 |
|
||
| `currEnd` | 当前这步跳跃能覆盖的最右边界 |
|
||
|
||
遍历数组时：
|
||
1. 对于每个位置 `i`，先更新 `maxReach = max(maxReach, i + nums[i])`。
|
||
2. 当 `i == currEnd` 时，说明当前这一步能到的所有位置都已考虑完毕，必须再跳一次，此时 `jumps++`，并将 `currEnd = maxReach`。
|
||
3. 当 `currEnd >= n - 1` 时，提前终止。
|
||
|
||
> [!abstract] 🔬 正确性证明
|
||
>
|
||
> 本题的贪心等价于**广度优先搜索（BFS）**的分层遍历：
|
||
>
|
||
> - **第 0 层**：起点 `{0}`，步数 = 0。
|
||
> - **第 1 层**：从第 0 层所有节点出发能一步到达的所有位置 `{1, ..., nums[0]}`，步数 = 1。
|
||
> - **第 k 层**：从第 k-1 层所有位置出发能一步到达、且尚未被访问过的位置，步数 = k。
|
||
>
|
||
> **贪心与 BFS 的等价性**：在第 k-1 层中，无论我们实际选哪个位置作为跳板，第 k 层覆盖的范围一定是 `∪{i + nums[i]} (i ∈ 第k-1层)` 的并集。而 `maxReach` 恰好就是这个并集的右端点。因此贪心算法每跳一次覆盖的范围，等同于 BFS 展开一层——两者得到的最小步数相同。
|
||
>
|
||
> **最优性**：BFS 保证第一次到达目标层时的层数就是最短距离（无权图最短路径的经典结论）。由于贪心算法的行为与 BFS 分层完全等价，所以它给出的跳跃次数也是最少的。证毕。
|
||
|
||
```mermaid
|
||
flowchart LR
|
||
A["开始\nmaxReach = 0\ncurrEnd = 0\njumps = 0"] --> B{"len(nums) == 1?"}
|
||
B -->|"是"| Z["返回 jumps(0)"]
|
||
B -->|"否"| C["for i = 0 to n-2"]
|
||
C --> D["maxReach = max(maxReach, i + nums[i])"]
|
||
D --> E{"i == currEnd?"}
|
||
E -->|"是"| F["jumps++\ncurrEnd = maxReach"]
|
||
F --> G{"currEnd >= n-1?"}
|
||
G -->|"是"| Y["返回 jumps"]
|
||
G -->|"否"| H{继续下一轮?}
|
||
E -->|"否"| H
|
||
H -->|"是"| C
|
||
H -->|"否"| Z
|
||
```
|
||
|
||
#### 逐步推演
|
||
|
||
以 `nums = [2, 3, 1, 1, 4]` 为例：
|
||
|
||
| i | nums[i] | maxReach 更新 | 是否 i == currEnd | jumps | currEnd | 说明 |
|
||
|---|---------|-------------|-------------------|-------|---------|------|
|
||
| 0 | 2 | max(0, 0+2) = 2 | ✅ 0 == 0 | 1 | 2 | 第 1 跳覆盖 [0, 2] |
|
||
| 1 | 3 | max(2, 1+3) = 4 | ❌ 1 ≠ 2 | 1 | 2 | 发现能从位置 1 直接跳到末尾 |
|
||
| 2 | 1 | max(4, 2+1) = 4 | ✅ 2 == 2 | **2** | 4 | 第 2 跳覆盖到索引 4，到达终点！ |
|
||
| — | — | — | — | — | — | **currEnd(4) ≥ n-1(4)，返回 jumps=2** |
|
||
|
||
用图示来看这个过程：
|
||
|
||
```
|
||
初始: [2, 3, 1, 1, 4]
|
||
↑ ↑
|
||
curr=0 target=4
|
||
|
||
第 1 跳范围 [0..2]: [■ ■ ■] ░ ░
|
||
0 1 2 maxReach 推到 4
|
||
|
||
第 2 跳范围 [2..4]: [■ ■ ■ ■ ■]
|
||
0 1 2 3 4 ← 到达目标！共跳 2 次
|
||
```
|
||
|
||
以 `nums = [2, 3, 0, 1, 4]` 为例：
|
||
|
||
| i | nums[i] | maxReach 更新 | 是否 i == currEnd | jumps | currEnd | 说明 |
|
||
|---|---------|-------------|-------------------|-------|---------|------|
|
||
| 0 | 2 | max(0, 0+2) = 2 | ✅ 0 == 0 | 1 | 2 | 第 1 跳覆盖 [0, 2] |
|
||
| 1 | 3 | max(2, 1+3) = 4 | ❌ 1 ≠ 2 | 1 | 2 | 从位置 1 能到索引 4 |
|
||
| 2 | 0 | max(4, 2+0) = 4 | ✅ 2 == 2 | **2** | 4 | 第 2 跳边界扩展到 4，已覆盖终点 |
|
||
| — | — | — | — | — | — | **currEnd(4) ≥ n-1(4)，返回 jumps=2** |
|
||
|
||
#### 为什么要遍历到 `n-2` 而不是 `n-1`？
|
||
|
||
因为题目保证一定能到达终点。当我们到达倒数第二个位置（`i = n-2`）并完成该步的跳跃计数后，`currEnd` 必然已经覆盖到 `n-1`，不需要再处理 `i = n-1` 本身。这样也能避免多计一次不必要的跳跃。
|
||
|
||
- **时间复杂度：O(n)** — 只需一次线性扫描，每个位置恰好访问一次
|
||
- **空间复杂度：O(1)** — 只使用三个整型变量
|
||
|
||
> [!note] 🐹 与跳跃游戏 I 的联系
|
||
> 两题共享同一个贪心框架（维护 `maxReach`），但跳跃游戏 II 多了 `currEnd` 和 `jumps` 两个变量来实现"分层计数"。可以把跳跃游戏 I 看作跳跃游戏 II 的简化版——少了一层 BFS 式的区间划分。
|
||
|
||
---
|
||
|
||
## 代码提示
|
||
|
||
```
|
||
// 伪代码模板
|
||
jumps = 0
|
||
currEnd = 0
|
||
maxReach = 0
|
||
|
||
for i from 0 to n-2: // 注意：只需遍历到倒数第二个位置
|
||
maxReach = max(maxReach, i + nums[i])
|
||
|
||
if i == currEnd: // 当前跳跃范围已到尽头，必须再跳
|
||
jumps++
|
||
currEnd = maxReach
|
||
|
||
// 优化：如果新边界已经覆盖终点，提前退出
|
||
if currEnd >= n - 1:
|
||
break
|
||
|
||
return jumps
|
||
```
|
||
|
||
Go 语言要点：
|
||
- 利用 `range` 遍历时自动跳过 `n-1`（通过 `i < len(nums)-1` 控制循环边界）。
|
||
- 使用 Go 1.21+ 内置的 `max` 函数。
|
||
- 题目保证一定有解，无需做不可达检查。
|
||
- 当 `n == 1` 时，起点即终点，返回 0。
|
||
|
||
---
|
||
|
||
## 技巧
|
||
|
||
> [!tip] 🔑 核心模式：BFS 分层贪心（Layered Greedy / Jump Pointers）
|
||
> 这是「用最少的段数覆盖整个序列」的一类问题的标准解法。典型特征：① 每个位置给出一个"向右延伸的能力值"；② 目标是用最少的"分段"覆盖 [0, n-1]。关键套路是用 `currEnd` 标记当前段的终点，到达时"切一刀"（jump++）并刷新边界。
|
||
|
||
> [!example] 🔗 同类问题
|
||
> - [55. 跳跃游戏](./78-跳跃游戏.md) —— 可行性判定版，同属一个贪心家族
|
||
> - [452. 用最少数量的箭引爆气球](../贪心算法/) —— 同样是区间覆盖类问题，贪心选择最优点
|
||
> - [56. 合并区间](../排序/) —— 区间合并的思想类似，都是通过比较边界做决策
|
||
> - [132. 分割回文串 II](../动态规划/) —— 「最少分割次数」同样使用分段 DP，思维结构一致
|
||
|
||
> [!warning] ⚠️ 常见陷阱
|
||
> 1. **遍历到 `n-1` 导致多计一次**：在终点位置触发 `i == currEnd` 会使 `jumps++`，但实际上我们已经到达了，不应该再多跳。所以循环应该只走到 `n-2`。
|
||
> 2. **把 `currEnd` 初始化为 `nums[0]`**：正确的初始化是 `currEnd = 0`，因为第一次跳跃是在位置 0 完成时才发生的。如果把 `currEnd` 设为 `nums[0]`，会在第一步就错误地触发 `jumps++`。
|
||
> 3. **忘记处理 `n == 1` 的边界情况**：单个元素时不需要任何跳跃，应返回 0。
|
||
|
||
> [!quote] 🧠 为什么这个贪心不是"局部最优 ≠ 全局最优"的反例？
|
||
> 乍看之下，我们在当前位置只选了"能让 `maxReach` 最大的那个跳板"，好像忽略了其他可能更优的路径。但关键在于：**我们并不是在做单次决策，而是在做一层决策。** 这一层内的所有位置都会被考虑到（通过不断更新 `maxReach`），最终只在这一层结束时才真正"做出选择"。这种"批量决策、延迟选择"的策略保证了全局最优。
|
||
|
||
> [!summary] 📊 跳跃游戏 I vs II 对比
|
||
> | 特征 | 55. Jump Game I | 45. Jump Game II |
|
||
> |------|----------------|-----------------|
|
||
> | 问题类型 | 可行性判定 | 最优值求解（最少步数） |
|
||
> | 核心变量 | `maxReach` | `maxReach` + `currEnd` + `jumps` |
|
||
> | 贪心粒度 | 逐个位置更新 | 按层（段）分组更新 |
|
||
> | 提前终止条件 | `maxReach >= n-1` | `currEnd >= n-1` |
|
||
> | 时间复杂度 | O(n) | O(n) |
|
||
> | 空间复杂度 | O(1) | O(1) |
|
||
|
||
---
|
||
|
||
## 代码
|
||
|
||
```go
|
||
// jump returns the minimum number of jumps to reach the last index.
|
||
// It uses a BFS-like greedy approach that processes positions in layers.
|
||
func jump(nums []int) int {
|
||
// ── Step 1: 边界处理 ──
|
||
// 只有一个元素时，起点即终点，不需要跳跃
|
||
n := len(nums)
|
||
if n == 1 {
|
||
return 0
|
||
}
|
||
|
||
// ── Step 2: 初始化三层状态 ──
|
||
jumps := 0 // 当前的跳跃次数
|
||
currEnd := 0 // 当前跳跃覆盖范围的右边界
|
||
maxReach := 0 // 从已访问位置出发能到达的最远索引
|
||
|
||
// ── Step 3: BFS 分层扫描（只需遍历到倒数第二个位置）──
|
||
for i := 0; i < n-1; i++ {
|
||
// 更新从任意已访问位置出发能到达的最远距离
|
||
maxReach = max(maxReach, i+nums[i])
|
||
|
||
// 当到达当前跳跃的边界时，必须发起下一次跳跃
|
||
if i == currEnd {
|
||
jumps++
|
||
currEnd = maxReach
|
||
|
||
// 优化：如果新边界已经覆盖终点，提前终止
|
||
if currEnd >= n-1 {
|
||
break
|
||
}
|
||
}
|
||
}
|
||
|
||
return jumps
|
||
}
|
||
```
|
||
|
||
> [!success] ✅ 运行验证
|
||
> - **LeetCode 第 45 题**，通过率约 40%，中等难度经典贪心题。
|
||
> - `nums = [2,3,1,1,4]` → `2`：第 1 跳覆盖 [0, 2]，在第 2 个位置发现 `maxReach=4`，第 2 跳直接到达终点。
|
||
> - `nums = [2,3,0,1,4]` → `2`：同上逻辑，即使位置 2 的值是 0 也不影响——因为我们是通过 `maxReach` 而非当前位置的值来决策。
|
||
> - `nums = [0]` → `0`：边界情况，单元素数组。
|
||
> - `nums = [1,1,1,1]` → `3`：每个位置只能跳 1 步，需要连续跳 n-1 次。
|
||
> - `nums = [4,1,1,3,1,1,1]` → `1`：第一个位置就能直接跳到末尾，只需一次跳跃。
|
||
> - **性能**：时间 O(n)，空间 O(1)。实际运行通常在 0ms ~ 4ms 之间（取决于数据规模），属于最优解。
|