算法

跳跃游戏 II

loser

22 Aug 2026 • 7 min read

给定一个长度为 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 步，然后从下标 1 跳 3 步到达数组的最后一个位置。

示例 2：

输入：nums = [2,3,0,1,4]
输出：2

提示：

1 <= nums.length <= 10^4
0 <= nums[i] <= 1000
题目保证可以到达 n - 1

贪心：

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();

        int steps = 0;
        int end = 0;
        int farthest = 0;

        for (int i = 0; i < n - 1; i++)
        {
            farthest = max(farthest, i + nums[i]);

            if (i == end)
            {
                steps++;
                end = farthest;
            }
        }

        return steps;
    }
};

核心思想

这题和“跳跃游戏”不同。

那道题只问能不能到达最后一个下标。

这道题要求最少跳几次到达最后一个下标。

如果真的枚举所有跳法，会有大量重复选择。

更好的做法是按“跳跃次数”分层。

这题最关键的观察是：

在当前跳跃次数能到达的所有位置中，下一跳应该尽量扩展到最远。

我们维护两个边界：

end：当前跳跃次数能够覆盖的最远位置
farthest：在当前覆盖范围内，再跳一步能够到达的最远位置

当遍历到 end 时，说明当前这一跳覆盖的范围已经扫描完。

这时必须再跳一次，于是：

steps++;
end = farthest;

变量含义

代码中有三个核心变量。

`steps`

steps 表示已经使用的跳跃次数。

每当当前覆盖范围扫描完，需要进入下一层范围时，就让 steps++。

`end`

end 表示用当前 steps 次跳跃，最远能够到达的位置。

也可以理解为当前这一层的右边界。

在遍历下标时，只要 i <= end，说明下标 i 属于当前跳跃次数能够覆盖的范围。

`farthest`

farthest 表示从当前层中的所有位置再跳一步，能够到达的最远位置。

遍历每个位置 i 时，用：

i + nums[i]

尝试更新它：

farthest = max(farthest, i + nums[i]);

为什么遍历到 `end` 时要跳一次

假设当前 end 是用 steps 次跳跃能到达的最远位置。

当遍历位置还没有超过 end 时，说明这些位置都属于当前跳跃次数能覆盖的范围。

我们在这个范围内不断更新 farthest，相当于提前看下一跳最多能到哪里。

当 i == end 时，当前这一层已经处理完。

如果还没有到终点，就必须再跳一次，进入下一层。

下一层的右边界就是刚才计算出的：

farthest

所以更新：

steps++;
end = farthest;

为什么循环只遍历到 `n - 2`

代码中循环条件是：

for (int i = 0; i < n - 1; i++)

也就是不遍历最后一个下标。

原因是：到达最后一个下标以后，就不需要再继续跳了。

如果把最后一个下标也放进循环，当 i == n - 1 且刚好等于 end 时，可能会多统计一次跳跃。

所以只需要考虑从哪些位置起跳。

最后一个下标是终点，不需要从它起跳。

为什么贪心是最少跳跃次数

每一次跳跃，都不是随便选择一个具体落点。

算法做的是：

把当前跳数能到达的位置全部看完
在这些位置中找出下一跳能到达的最远边界
然后统一进入下一跳

这等价于广度优先搜索中的一层一层扩展。

当前层中的所有位置，都可以用相同的跳跃次数到达。

下一层是再跳一次能够到达的位置。

因此第一次覆盖到终点时，使用的跳跃次数一定最少。

而 farthest 取最大值，只是在当前层内保留最远的下一层边界，不会错过更优答案。

边界情况

如果数组长度为 1：

nums = [0]

一开始就在最后一个下标，不需要跳跃。

代码中循环不会执行，steps 保持为 0，返回 0。

题目保证一定可以到达 n - 1，所以不需要额外处理无法到达的情况。

如果数组中存在 0，也不一定有问题。

例如：

nums = [2,3,0,1,4]

虽然下标 2 的值是 0，但可以通过下标 1 继续跳到更远的位置。

贪心维护的是当前范围内所有位置的最远扩展，不会被单个 0 卡住。

正确性证明

我们证明：算法返回的 steps 是到达最后一个下标所需的最小跳跃次数。

结论 1：`end` 表示当前跳跃次数能到达的最远下标

初始时，steps = 0，还没有跳跃，只能位于下标 0。

所以：

end = 0

成立。

当扫描完当前范围 [0, end] 后，farthest 已经记录了从这些位置再跳一步能到达的最远下标。

此时执行：

steps++;
end = farthest;

就表示多跳一次以后，能覆盖到的新最远下标是 farthest。

所以每次更新后，end 仍然表示当前跳跃次数能到达的最远下标。

结论 2：`farthest` 表示下一跳能到达的最远下标

在当前层范围内，每个位置 i 都可以由当前跳跃次数到达。

从位置 i 再跳一步，最远可以到达：

i + nums[i]

算法对当前层所有位置都执行：

farthest = max(farthest, i + nums[i]);

所以当前层扫描结束时，farthest 就是下一跳能够到达的最远下标。

结论 3：每次 `steps++` 都是必要的一次跳跃

当 i == end 时，当前跳跃次数能够覆盖的位置已经全部扫描完。

如果还要继续到达更远的位置，就必须再跳一次。

算法此时执行 steps++，正好对应进入下一层可达范围。

因此每次增加跳跃次数都是必要的，不会多加无意义的跳跃。

结论 4：算法不会错过更少跳数的方案

算法按照跳跃次数分层处理。

用 steps 次能到达的所有位置，都在当前层中被扫描。

只有当前层扫描完以后，才会进入 steps + 1 次跳跃能够到达的范围。

因此如果存在用更少跳数到达终点的方案，终点一定会在更早的某一层被覆盖。

算法不会跳过这一层。

所以最终得到的 steps 一定是最小跳跃次数。

得出结论

由结论 1 可知，end 正确表示当前跳数的覆盖边界。

由结论 2 可知，farthest 正确记录下一跳的最远边界。

由结论 3 可知，跳跃次数的增加时机正确。

由结论 4 可知，算法不会错过更少跳数的方案。

因此算法正确。

举例理解

以：

nums = [2,3,1,1,4]

为例。

初始：

steps = 0
end = 0
farthest = 0

遍历过程：

下标	当前值	更新后 `farthest`	是否到达 `end`	操作
`0`	`2`	`2`	是	`steps = 1, end = 2`
`1`	`3`	`4`	否	继续扫描当前层
`2`	`1`	`4`	是	`steps = 2, end = 4`

此时 end 已经覆盖最后一个下标。

最终答案是：

2

对应跳法是：

0 -> 1 -> 4

复杂度分析

数组最多被遍历一次。

每个位置只做常数次更新。

所以时间复杂度是：

O(n)

算法只使用 steps、end、farthest 三个变量。

所以空间复杂度是：

`O(1)

贪心：