跳跃游戏
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给你一个非负整数数组 nums，你最初位于数组的 第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true；否则，返回 false。
示例 1
示例 2
模拟答题者思考
1. 最直接：从每个位置 DFS/BFS 枚举所有合法跳跃路径，看能否到达 n-1，状态空间指数级，n=10⁴ 会超时。
2. 重复在哪里？「从位置 i 能否到达终点」会被反复计算——典型 DP：dp[i] = any(dp[j]) 对所有 j<i 且 j+nums[j]≥i，朴素 O(n²)。
3. 换个视角：我们不需要知道「最少几步」，只需知道「最远能到哪」——从左到右扫描，维护一个全局最远可达下标 farthest。
4. 贪心关键：若当前 i > farthest，说明连位置 i 都到不了，后面更不可能；否则用 i + nums[i] 扩展 farthest，扫完后看 farthest 是否 ≥ n-1。
5. 正确性直觉：farthest 单调不减，且包含了「从起点经任意合法路径能到达的所有位置」的上界；一旦 farthest ≥ n-1 即存在一条路径到终点。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
farthest | int | 定义：从起点出发，经过若干次合法跳跃后，最远能到达的下标（含该位置） 维护：从左到右扫描时，每到一个可达位置 i，用 i + nums[i] 尝试扩展 farthest更新： farthest = max(farthest, i + nums[i])；若最终 farthest ≥ n-1 则可达终点 |
i | int | 定义：从左到右扫描的下标，代表「当前正在考察的落脚点」 维护： for i in range(n)，只处理 i ≤ farthest 的位置（超出则说明此点不可达）更新：每轮用 nums[i] 更新 farthest；若 i > farthest 提前返回 false |
nums[i] | int | 定义：从下标 i 出发单次跳跃的最大步长维护：仅当 i 可达（i ≤ farthest）时才参与扩展更新：与 i 相加得到从 i 出发能跳到的最远下标，用于刷新 farthest |
落码步骤
1. 初始化 farthest = 0，n = len(nums)
2. 遍历 i 从 0 到 n-1
3. 若 i > farthest，说明当前位置不可达，返回 false
4. 更新 farthest = max(farthest, i + nums[i])
5. 若 farthest ≥ n-1，可提前返回 true（可选优化）
6. 循环结束返回 true（能扫完说明终点可达）
代码实现
class Solution:
def canJump(self, nums: List[int]) -> bool:
farthest = 0
n = len(nums)
for i in range(n):
if i > farthest:
return False
farthest = max(farthest, i + nums[i])
if farthest >= n - 1:
return True
return Trueclass Solution {
public:
bool canJump(vector<int>& nums) {
int farthest = 0;
int n = nums.size();
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;
}
};
// 时间 O(n)，空间 O(1)复杂度分析
O(n)
O(1)
常见坑
忘记判断 i > farthest：只更新 farthest 而不检查当前位置是否可达，会在 [3,2,1,0,4] 这类用例上误判为 true。
本题求能否到达，与 #45「跳跃游戏 II」（求最少跳跃次数）不同；后者需要按层结算 steps，不能混用。
nums[i] 可以为 0：站在 0 步长处仍算「到达该位置」，只是无法继续向前扩展 farthest。
必测边界 Case
nums = [0] → true（已在终点，无需跳跃）
nums = [1, 0] → true（从下标 0 跳 1 步到终点）
nums = [3, 2, 1, 0, 4] → false（最远只能到下标 3，nums[3]=0 无法继续前进）
nums = [2, 0, 0, 1] → true（经过若干 0 步长位置仍可到达终点）
nums = [5, 0, 0, 0, 0] → true（第一步即可覆盖全程）