55. 跳跃游戏

55. 跳跃游戏

✨核心逻辑

本题采用 贪心算法 的策略:

  1. 最大化覆盖范围:不必纠结于具体要跳几步,只需要维护一个变量 maxReach,表示当前能到达的最远位置。
  2. 遍历判断:从数组的第一个位置开始遍历。如果遍历到的当前下标 i 超出了我们目前能到达的最远位置 maxReach,说明中间出现了断层,无法跳跃到达终点,直接返回 false
  3. 更新覆盖范围:对于每一个可达的位置 i,计算从该位置能跳到的最大距离 i + nums[i],并更新全局最远可达距离 maxReach
  4. 提前结束:一旦发现 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 好”。因为只要某个索引在你能跳到的范围内,你就一定能踩上去。我们关注的不是某一步跳到哪,而是整个过程中,最远能推进到哪