算法

跳跃游戏

loser

22 Aug 2026 • 6 min read

给你一个非负整数数组 nums。

你最初位于数组的第一个下标。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

如果可以，返回 true；否则，返回 false。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1，然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。
但该下标的最大跳跃长度是 0，所以永远不可能到达最后一个下标。

提示：

1 <= nums.length <= 10^4
0 <= nums[i] <= 10^5

贪心：

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        int farthest = 0;

        for (int i = 0; i < n; i++)
        {
            if (i > farthest)
            {
                return false;
            }

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

            if (farthest >= n - 1)
            {
                return true;
            }
        }

        return true;
    }
};

核心思想

这题不需要真的模拟每一种跳法。

我们只需要关心一件事：

从已经能够到达的位置出发，最远可以扩展到哪里。

用变量 farthest 表示当前能够到达的最远下标。

遍历数组时，如果当前位置 i 可以到达，也就是：

i <= farthest

那么就可以从位置 i 出发，再尝试更新最远可达位置：

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

如果某个位置 i 已经大于 farthest，说明无论之前怎么跳，都到不了这个位置。

这时后面的下标也就无法继续从这里扩展，直接返回 false。

为什么维护最远可达下标就够了

假设当前已经处理过 [0, i] 范围内的位置。

只要这些位置中有一些可以到达，那么从它们出发能到达的所有位置，会形成一个从左到右连续扩展的可达范围。

我们不需要记录“具体怎么跳过来”。

因为题目只问能不能到达最后一个下标，不问路径。

所以对每个可达位置 i，只要看它能把边界扩展到哪里：

i + nums[i]

然后取最大值即可。

如果最终 farthest >= n - 1，说明最后一个下标已经在可达范围内，返回 true。

为什么遇到 `i > farthest` 就一定失败

farthest 表示从前面所有可达位置出发，最远能到达的下标。

如果遍历到某个位置 i 时：

i > farthest

说明位置 i 不在当前可达范围内。

也就是说，从前面的任何位置出发，都跳不到 i。

既然到不了 i，就更不可能利用 nums[i] 去继续向后跳。

所以此时可以确定无法到达最后一个下标，直接返回 false。

为什么贪心选择是安全的

这题的贪心不是每次选择“跳到哪个位置”，而是每次维护“当前能到达的最远边界”。

对于所有已经可达的位置，它们都可以作为下一次起跳点。

其中某个位置能扩展得更远，只会让后续选择更多，不会让答案变差。

因此保留最大的 farthest 就足够了。

如果一个位置没有让 farthest 变大，也不影响结果，因为它能到达的范围已经被之前的某个位置覆盖。

边界情况

如果数组长度为 1，一开始就在最后一个下标。

此时答案一定是 true。

代码中：

farthest >= n - 1

在第一轮就会成立。

如果数组中存在 0，并不一定失败。

例如：

nums = [2,0,0]

可以从下标 0 直接跳到最后一个下标。

真正失败的情况是：某个 0 或者一段无法跨过的位置，让 farthest 停住，而后面的下标又大于 farthest。

例如：

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

最多只能到达下标 3，无法越过它到达下标 4。

正确性证明

我们证明：算法返回的结果满足题意。

结论 1：遍历过程中，`farthest` 始终表示从已处理的可达位置出发能到达的最远下标

初始时位于下标 0，所以 farthest = 0。

当遍历到位置 i 时，如果 i <= farthest，说明位置 i 可以到达。

从位置 i 出发，最远可以到达：

i + nums[i]

因此更新：

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

就能把当前位置的跳跃能力纳入考虑。

如果 i > farthest，说明位置 i 不可达，不应该用它更新边界。

所以 farthest 的含义始终正确。

结论 2：如果算法返回 `true`，一定可以到达最后一个下标

算法返回 true 的条件是：

farthest >= n - 1

根据结论 1，farthest 表示从已处理的可达位置出发能到达的最远下标。

如果它已经覆盖最后一个下标 n - 1，说明存在某种跳法可以到达最后一个下标。

因此返回 true 正确。

结论 3：如果算法返回 `false`，一定无法到达最后一个下标

算法返回 false 的条件是遇到某个位置：

i > farthest

根据结论 1，前面所有可达位置最多只能到达 farthest。

既然 i 已经超过 farthest，说明无法到达位置 i。

而数组下标只能从左往右跳，无法跳过不可达断点后继续扩展。

所以最后一个下标也不可能到达。

因此返回 false 正确。

得出结论

由结论 1 可知，算法维护的最远可达范围始终正确。

由结论 2 可知，算法返回 true 时确实可以到达终点。

由结论 3 可知，算法返回 false 时确实无法到达终点。

因此算法正确。

举例理解

以：

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

为例。

下标	当前值	更新前最远可达	更新后最远可达
`0`	`2`	`0`	`2`
`1`	`3`	`2`	`4`

当 farthest = 4 时，已经可以到达最后一个下标，所以返回 true。

再看：

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

遍历过程：

下标 0 可以到达，最远更新到 3
下标 1 可以到达，最远仍然是 3
下标 2 可以到达，最远仍然是 3
下标 3 可以到达，但 nums[3] = 0，最远仍然是 3
到下标 4 时，4 > farthest

说明下标 4 不可达，所以返回 false。

复杂度分析

数组最多被遍历一次。

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

所以时间复杂度是：

O(n)

算法只使用一个变量 farthest。

所以空间复杂度是：

`O(1)

贪心：