12 KiB
tags, create time
| tags | 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 |
当前这步跳跃能覆盖的最右边界 |
遍历数组时：
- 对于每个位置
i，先更新maxReach = max(maxReach, i + nums[i])。 - 当
i == currEnd时，说明当前这一步能到的所有位置都已考虑完毕，必须再跳一次，此时jumps++，并将currEnd = maxReach。 - 当
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 分层完全等价，所以它给出的跳跃次数也是最少的。证毕。
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. 跳跃游戏 —— 可行性判定版，同属一个贪心家族
- 452. 用最少数量的箭引爆气球 —— 同样是区间覆盖类问题，贪心选择最优点
- 56. 合并区间 —— 区间合并的思想类似，都是通过比较边界做决策
- 132. 分割回文串 II —— 「最少分割次数」同样使用分段 DP，思维结构一致
[!warning] ⚠️ 常见陷阱
- 遍历到
n-1导致多计一次：在终点位置触发i == currEnd会使jumps++，但实际上我们已经到达了，不应该再多跳。所以循环应该只走到n-2。- 把
currEnd初始化为nums[0]：正确的初始化是currEnd = 0，因为第一次跳跃是在位置 0 完成时才发生的。如果把currEnd设为nums[0]，会在第一步就错误地触发jumps++。- 忘记处理
n == 1的边界情况：单个元素时不需要任何跳跃，应返回 0。
[!quote] 🧠 为什么这个贪心不是"局部最优 ≠ 全局最优"的反例？ 乍看之下，我们在当前位置只选了"能让
maxReach最大的那个跳板"，好像忽略了其他可能更优的路径。但关键在于：我们并不是在做单次决策，而是在做一层决策。 这一层内的所有位置都会被考虑到（通过不断更新maxReach），最终只在这一层结束时才真正"做出选择"。这种"批量决策、延迟选择"的策略保证了全局最优。
[!summary] 📊 跳跃游戏 I vs II 对比
特征 55. Jump Game I 45. Jump Game II 问题类型 可行性判定 最优值求解（最少步数） 核心变量 maxReachmaxReach+currEnd+jumps贪心粒度 逐个位置更新 按层（段）分组更新 提前终止条件 maxReach >= n-1currEnd >= n-1时间复杂度 O(n) O(n) 空间复杂度 O(1) O(1)
代码
// 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 之间（取决于数据规模），属于最优解。