--- 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 之间（取决于数据规模），属于最优解。