55. 跳跃游戏
✨核心逻辑
本题采用 贪心算法 的策略:
- 最大化覆盖范围:不必纠结于具体要跳几步,只需要维护一个变量
maxReach,表示当前能到达的最远位置。 - 遍历判断:从数组的第一个位置开始遍历。如果遍历到的当前下标
i超出了我们目前能到达的最远位置maxReach,说明中间出现了断层,无法跳跃到达终点,直接返回false。 - 更新覆盖范围:对于每一个可达的位置
i,计算从该位置能跳到的最大距离i + nums[i],并更新全局最远可达距离maxReach。 - 提前结束:一旦发现
maxReach已经大于等于数组的最后一个下标n-1,说明已经可以成功跳到终点,立刻返回true。
🔥代码实现(含详细变量注释)
class Solution {
public boolean canJump(int[] nums) {
// 边界情况:如果数组只有一个元素,初始就位于最后一个下标,直接返回 true
if (nums.length == 1) {
return true;
}
// maxReach:贪心策略中的核心变量,记录当前能够到达的最远索引位置(最大覆盖范围)
int maxReach = 0;
// n:记录数组的长度
int n = nums.length;
// i:遍历指针,用于从前往后扫描数组中的每一个下标
for (int i = 0; i < n; i++) {
// 关键判断:如果当前遍历到的下标 i,已经超出了我们目前能到达的最远位置 maxReach
// 说明中间存在无法跨越的障碍,无法到达当前位置,因此永远无法到达终点
if (i > maxReach) {
return false;
}
// 更新最大覆盖范围:计算从当前位置 i 能跳到的最大距离 `i + nums[i]`,
// 并与当前记录的 `maxReach` 进行比较,取较大值
maxReach = Math.max(maxReach, i + nums[i]);
// 如果当前的最大覆盖范围已经大于或等于数组最后一个元素的下标 n-1
// 说明跳跃已经能够覆盖到终点,直接提前结束并返回 true
if (maxReach >= n - 1) {
return true;
}
}
// 如果遍历结束还没有返回,则说明无法到达终点(通常逻辑不会走到这里,代码为了完整性保留)
return false;
}
}
⏱️复杂度分析
- 时间复杂度:O(N),其中 N 是数组的长度。我们只需要一次遍历数组,在循环内部进行常数次的判断和更新操作。
- 空间复杂度:O(1),只使用了两个额外的整型变量 maxReach 和 n,没有占用额外的数组或递归栈空间。
🐛反思一下:
最开始认为我觉得有很多种选择,比方说当前的索引的值是x,我可以跳 0 - x-1 的中任意步伐,每一个索引的值都是如此,选择性很多无从下手
每一个点都有多种跳跃选择,如果你去模拟“跳到哪个索引,然后再从这个索引继续怎么跳”,思路就会立刻变成一棵巨大的搜索树,代码不仅难写,而且必然会超时(时间复杂度会是指数级的
用“贪心算法”追踪“最远能覆盖到的范围”即可
不要纠结“我从索引 2 是跳到索引 3 好,还是跳到索引 5 好”。因为只要某个索引在你能跳到的范围内,你就一定能踩上去。我们关注的不是某一步跳到哪,而是整个过程中,最远能推进到哪