本文概览：本文讲解跳跃游戏 II 的两种贪心写法——分层遍历（一跳一层，无需选落点）和落点选择（每次跳到能到最远的落点），本质都是"每跳取最远可达"

一、题目

跳跃游戏 II 题目图片

二、题目分析

1. 题目要求

给定一个非负整数数组 nums，最初位于下标 0，每个元素代表在该位置能往前跳的最大步数。题目保证总是可以到达最后一个下标，求到达终点的最少跳跃次数。

例子：nums = [2, 3, 1, 1, 4]

1
2
0  1  2  3  4        ← 索引
2  3  1  1  4        ← 值

最少 2 跳：从下标 0 跳 1 步到下标 1（值 3），再跳 3 步到终点下标 4。

和跳跃游戏 I 的区别：

  • 跳跃游戏 I：判断能不能到终点
  • 跳跃游戏 II：必然能到终点，求最少几跳

2. 核心工具还是"最远可达距离"

跳跃游戏 I 靠"最远可达距离 maxDistance"判断能不能到末尾。这题怎么利用它？

关键事实：既然必然能到终点，那么每一跳都跳到"当前能到的最远位置"，整体就是最少跳数——每一跳都把进度推到最大，跳数自然最少。这是贪心思想。

基于这个事实，有两种编写视角，本质一样，写法不同：

  • 方法一：分层遍历——把跳跃看成一层一层（隐式 BFS），一跳就是一层，走完一层跳数加一，无需选择落点
  • 方法二：落点选择——真正模拟每一跳，站在落点上枚举候选，选"经过它能到最远"的那个落点跳过去

方法二直观好理解但代码边界多；方法一不需要选落点，顺序遍历完整走完就好，代码好写。下面两种都讲解。

三、思路概览

方法一：分层遍历（推荐，好写）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int jump(int[] nums) {
    int len = nums.length;
    if (len <= 1) return 0;

    int jumps = 0;
    int curEnd = 0;      // 当前跳跃能覆盖的最远下标（当前层右边界）
    int curFarthest = 0; // 在当前层范围内，能到达的最远距离（下一层右边界）

    for (int i = 0; i < len - 1; i++) {
        // 不断更新下一层能到达的最远距离
        curFarthest = Math.max(curFarthest, i + nums[i]);

        // 走到当前层右边界 → 必须再跳一次
        if (i == curEnd) {
            jumps++;
            curEnd = curFarthest;

            // 提前终止：下一层已经能覆盖终点
            if (curEnd >= len - 1) break;
        }
    }
    return jumps;
}

思路简要说明：

  1. curEnd：当前这一跳能覆盖的右边界（当前层的范围终点）
  2. curFarthest：遍历当前层的过程中，不断刷新的"下一层右边界"
  3. i == curEnd 时：当前层走完了，必须再跳一次 → jumps++，进入下一层（curEnd = curFarthest）
  4. curEnd >= len - 1：下一层已覆盖终点，提前结束
  5. **时间复杂度 O(n)**：一遍遍历

方法二：落点选择（直观，边界多）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public int jump(int[] nums) {
    int len = nums.length;
    if (len == 1) {
        return 0;
    }
    int maxDistance = nums[0];
    int index = 0;
    int jump = 0;
    while (index < len) {
        int distance = nums[index];
        int newIndex = index;
        // 当前落点一步就能到终点 → 收尾
        if (index + distance >= len - 1) {
            return ++jump;
        }
        // 枚举候选落点，选"经过它能到最远"的
        for (int i = 1; i < distance + 1; i++) {
            if (index + nums[index + i] + i > maxDistance) {
                maxDistance = index + nums[index + i] + i;
                newIndex = index + i;
                if (maxDistance >= len - 1) {
                    break;
                }
            }
        }
        index = newIndex;
        jump++;
    }
    return jump;
}

思路简要说明：

  1. 站在落点 index：先看 index + nums[index] 是否直接覆盖终点，是就收尾
  2. 枚举候选落点：index+1 到 index+nums[index]，计算每个候选 j 的"经过它最远到 j + nums[j]"
  3. 跳到最优落点：选能刷新 maxDistance 的那个，jump++
  4. 循环直到收尾：题目保证必然可达，最后一轮一定走 return

四、思路详解

方法一：分层遍历

第一步：把跳跃看成一层一层

从索引 0（值 2）出发，落点可以是索引 1 或索引 2——这些落点合在一起就是第 1 跳的可达范围，像一个"层"：

1
2
3
4
5
0  1  2  3  4        ← 索引
2  3  1  1  4        ← 值

第1跳可达（从0出发）:    [1, 2]
第2跳可达（从1或2出发）:  [3, 4]     ← 覆盖终点 → 2跳
  • 第 1 跳的落点范围由 0 + nums[0] = 2 决定，即 (0, 2]
  • 遍历索引 1、2 时，能到的最远被刷新为 1 + nums[1] = 4，这就是第 2 跳的右边界
  • 第 2 跳的落点范围是 (2, 4]，4 已覆盖终点

**每一层就是"固定跳数下的全部可达位置"**，这其实就是 BFS 的分层思想：第 k 层 = k 跳能到的所有位置。

第二步：层的右边界怎么转移？

用两个变量：

  • curEnd：当前层的右边界
  • curFarthest：遍历当前层的过程中，不断被刷新的"最远可达"，它就是下一层的右边界
1
2
3
遍历第1层（i 在 (0, 2] 内）:
  i=1: curFarthest = max(2, 1+3) = 4   ← 索引1贡献了下一层的右边界
  i=2: curFarthest = max(4, 2+1) = 4

每个位置 i 都贡献自己的 i + nums[i]，取最大值——和跳跃游戏 I 的 maxDistance 一模一样，只是这里它是分层的：走完一层才结算一次。

第三步：什么时候 jumps++？

当 i == curEnd，说明当前层的范围已经走完，再往后走必然需要再跳一次：

1
2
jumps++            ← 多跳一次
curEnd = curFarthest ← 进入下一层，右边界换成遍历中攒出来的最远

这就是"一次遍历、无需选择落点"的原因：我们从不关心具体落在哪，只要顺序扫过去，扫完一层自动结算一跳。每层的右边界取的都是该层所有位置贡献的最大值——每一跳都跳到最远，贪心就藏在层的定义里。

完整执行过程

以 nums = [2, 3, 1, 1, 4] 为例（len = 5，终点下标 4）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
初始：jumps=0, curEnd=0, curFarthest=0

i=0, 值2：
  curFarthest = max(0, 0+2) = 2
  i==curEnd(0) → 走完第0层
    jumps=1, curEnd=2        ← 第1跳的右边界
    2 < 4，继续

i=1, 值3：
  curFarthest = max(2, 1+3) = 4
  1 != curEnd(2)，继续攒

i=2, 值1：
  curFarthest = max(4, 2+1) = 4
  i==curEnd(2) → 走完第1层
    jumps=2, curEnd=4        ← 第2跳的右边界
    4 >= 4 → break           ← 覆盖终点

返回 jumps = 2 ✓
（对应 0 → 1 → 4，但代码里从没记录过落点）

方法二：落点选择

第一步：每次跳跃怎么选落点？

站在落点 index，候选落点是 index+1 到 index+nums[index]。选哪个？

选"经过它能到最远"的那个。比如从索引 0 出发：

1
2
3
4
5
6
7
0  1  2  3  4        ← 索引
2  3  1  1  4        ← 值

候选落点:        1(值3)   2(值1)
经过它最远到:    1+3=4    2+1=3
                  ↑
            选落点1，能到最远

为什么这样对？因为落点选远的，下一跳的起点就更靠后、覆盖更远，总跳数只会更少不会更多——这就是"每一跳都取最远可达"的直接体现。

第二步：代码里的关键细节

收尾判断：每次落地先检查 index + distance >= len - 1，当前落点一步就能到终点，直接 return ++jump，不用再枚举。

候选计算：index + nums[index + i] + i 拆开看——

1
2
3
4
index + i          ← 候选落点的下标
+ nums[index + i]  ← 从候选落点还能跳多远

整体 = 经过该候选，从当前落点出发两跳的进度

maxDistance 跨轮次维护：它只增不减，记录的是"到目前为止见过的最远可达"。候选只有能刷新它才值得跳（否则有更远的走法覆盖了它）。

完整执行过程

以 nums = [2, 3, 1, 1, 4] 为例（len = 5）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
初始：maxDistance=nums[0]=2, index=0, jump=0

第1轮 while（index=0）：
  distance = nums[0] = 2
  0 + 2 = 2 < 4，不能收尾
  枚举候选 i=1..2：
    i=1: 0+nums[1]+1 = 0+3+1 = 4 > 2 → maxDistance=4, newIndex=1
         4 >= 4 → break
    （i=2 没轮到，已经够了）
  index=1, jump=1

第2轮 while（index=1）：
  distance = nums[1] = 3
  1 + 3 = 4 >= 4 → 当前落点一步到终点
  return ++jump = 2 ✓

两种思路的对比

维度 方法一：分层遍历 方法二：落点选择
视角 隐式 BFS，一跳一层 真实模拟每一跳
是否选落点 不选，顺序扫完一层自动结算 每跳枚举候选选最优
代码量 短，边界少 长，边界多（收尾、枚举、break）
本质 每层右边界取层内贡献的最大值 每跳选能到最远的落点
复杂度 O(n) / O(1) O(n) / O(1)（每轮枚举的候选总数不超 n）

本质完全一样：都是"每一跳取最远可达"。方法一把选择藏在层的结算里，方法二把选择明写在枚举里。理解了本质，推荐写方法一——不需要处理落点的边界，一遍遍历完整走完就好。

复杂度分析

**时间复杂度 O(n)**：两种方法都是每个索引常数次处理。

**空间复杂度 O(1)**：常数个变量。

五、总结

跳跃游戏 II 的核心思路：

  1. 题目前提：必然可达，求最少跳数
  2. 贪心策略：每一跳都取"能到的最远位置"，跳数自然最少
  3. 方法一（分层遍历）：curEnd 是当前层右边界，curFarthest 攒下一层右边界，i == curEnd 时 jumps++ 并换层，无需选落点
  4. 方法二（落点选择）：每跳枚举候选落点，选"经过它两跳进度最大"的跳过去，当前落点能一步到终点就收尾
  5. 推荐方法一：边界少、好写，本质相同

和跳跃游戏 I 的关系：I 用 maxDistance 判断"能不能到"，II 用同样的最远可达"数跳数"。I 是 II 的基础工具，II 是 I 的进阶应用——一个变量从"判可达"升级成了"分层计数"。

BFS 分层的思想在这里体现得很纯粹：**"最少跳数" = "最短路径"，层就是步数**。遇到"求最少操作次数"类问题，想想能不能把状态按操作次数分层，一层一层往外扩。