LeetCode 55. 跳跃游戏
题目描述
✅ 55. 跳跃游戏
题意分析
从下标
0出发，nums[i]表示在位置i最多能向右跳多少步，可以选择不超过这个上限的步数，不要求每次都跳满。判断是否存在一条路线到达最后一个下标，返回布尔值。数组非空，元素均为非负数；零表示不能从该位置继续向右跳，但可以从更早的位置越过它。只要求判断可达性，不需要给出路线或最少跳数；只有一个元素时，起点已经是终点。
解法：贪心维护最远可达下标
核心思路
[!blue]
从一个可达位置出发，可以选择任意不超过上限的跳跃长度，因此能新增的是一整段连续位置。起点天然可达，每次扩张又与已有可达区间相接，所以可达位置始终构成从
0开始的连续前缀，只记录最远边界maxReach就足够。从左向右考察
i。若i <= maxReach，说明之前已经找到某条路线到达这里，于是可以继续跳到最远的i + nums[i]，用它与旧边界取最大值。这里是在合并所有可达路线的能力，并不是要求实际路线逐个经过这些下标。若
i > maxReach，此前所有可达位置的跳跃能力都已经检查，却仍无法到达i。任何更右的位置也无法越过这段缺口，不能拿它们的数值来扩张边界，所以可以直接返回失败。一旦
maxReach >= n - 1就能返回成功。即使某次跳跃的最大落点越过终点，也可以少跳几步恰好到达末尾。整个过程只需把已可达位置的能力合并到一个不回退的右边界，无需枚举路线。
解题步骤
- 初始化
maxReach = 0，表示起点天然可达。- 从左到右遍历下标
i；若i > maxReach，当前位置不可达，返回false。- 当前位置可达时，用
maxReach = max(maxReach, i + nums[i])扩展最远边界。- 若边界已经覆盖
n - 1，提前返回true。
代码实现
class Solution {
public boolean canJump(int[] nums) {
int maxReach = 0;
for (int i = 0; i < nums.length; i++) {
// 先确认当前位置可达，不能让缺口后的值参与扩展。
if (i > maxReach) {
return false;
}
// 保留已有最远边界，较短的新跳跃不能让边界倒退。
maxReach = Math.max(maxReach, i + nums[i]);
if (maxReach >= nums.length - 1) {
return true;
}
}
return true;
}
}
func canJump(nums []int) bool {
maxReach := 0
for i := 0; i < len(nums); i++ {
// 先确认当前位置可达，不能让缺口后的值参与扩展。
if i > maxReach {
return false
}
reach := i + nums[i]
// 保留已有最远边界，较短的新跳跃不能让边界倒退。
if reach > maxReach {
maxReach = reach
}
if maxReach >= len(nums)-1 {
return true
}
}
return true
}
复杂度分析
- 时间复杂度：$O(n)$，每个下标最多访问一次。
- 空间复杂度：$O(1)$，只维护最远可达边界。
关键点总结
[!green]
- 可达集合是连续前缀，因此一维边界足以替代整张 DP 表。
- 更新顺序必须是“先确认当前位置可达，再用它扩展边界”。
- 本题只问可达性；若追问最少跳数，需要像 45 题那样额外维护当前跳跃边界并分层计步。
易错点总结
[!yellow]
- 必须先判断
i > maxReach，不可达位置即使存着很大的跳跃长度，也不能帮助越过缺口。- 不能见到零就失败，之前的跳跃可能已经覆盖它后面的位置；是否失败取决于可达边界。
- 不可达条件是
i > maxReach，不是i >= maxReach；边界位置本身仍然可达。- 更新要取最大值，不能直接赋值为
i + nums[i]，否则较弱的后续位置可能让边界倒退。- 单元素数组的起点就是终点，即使该元素为零，也应返回
true。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 45. 跳跃游戏 II | 中等 | 可达右边界的维护相同，原题还按边界扩张的轮次统计最少跳跃次数。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！