力扣（跳跃游戏I/II）

一、LeetCode 55. 跳跃游戏——判断能否到达终点

（一）题目剖析：能否抵达终点的判断

给定一个非负整数数组 nums，初始位于数组第一个下标，数组中每个元素代表在该位置可跳跃的最大长度。需判断是否能够到达最后一个下标，核心是在遍历过程中，动态维护能到达的最远位置，看是否能覆盖到数组末尾。

（二）算法思想：贪心算法的动态覆盖

贪心算法在此题的应用，体现在动态维护能到达的最远位置 maxReach 。遍历数组时，每一步都尽可能拓展能到达的范围：

• 若当前下标 i 在可到达范围内（i <= maxReach ），则更新 maxReach 为 max(maxReach, i + nums[i]) ，代表从当前位置起跳能到达的更远位置。
• 一旦 maxReach 大于等于数组最后一个下标，直接返回 true ，因为已能确定可以到达终点；若遍历到某个下标时，发现 i > maxReach ，说明无法继续前进，返回 false 。通过这样每一步都做当前最优的拓展选择，实现全局能否到达终点的判断。

（三）代码实现与注释解析

class Solution {
    public boolean canJump(int[] nums) {
        // 记录当前能到达的最远索引，初始为 0（起始位置）
        int maxReach = 0; 
        // 数组的最后一个位置下标，即目标位置
        int target = nums.length - 1; 
        
        for (int i = 0; i < nums.length; i++) { 
            // 如果当前索引超过了能到达的最远位置，说明无法继续前进，返回 false
            if (i > maxReach) { 
                return false; 
            }
            // 更新能到达的最远位置，取之前的最远位置和从当前位置起跳能到的位置的最大值
            maxReach = Math.max(maxReach, i + nums[i]); 
            // 如果已经能到达或超过最后一个位置，直接返回 true
            if (maxReach >= target) { 
                return true; 
            }
        }
        // 循环结束后仍未到达终点（理论上若能遍历完数组，说明前面没提前返回，这种情况较少，比如数组全 0 但长度 1 已处理 ）
        return false; 
    }
}

代码执行流程

1. 初始化变量：maxReach 初始化为 0 ，代表起始位置能到达的最远索引；target 设为数组最后一个元素的下标，明确目标。
2. 遍历数组：逐个遍历数组元素，对于每个下标 i ：
   • 若 i > maxReach ，说明当前位置已超出能到达的范围，无法继续，返回 false 。
   • 否则，更新 maxReach ，尝试拓展能到达的最远位置。
   • 若更新后的 maxReach >= target ，说明已能到达或超过终点，直接返回 true ，提前结束判断。
3. 循环结束处理：若循环正常结束（未提前返回 true ），说明遍历完数组都没到达终点，返回 false （实际中若数组有效，大多会在遍历中提前返回 ）。

（四）复杂度分析

• 时间复杂度：仅需遍历一次数组，时间复杂度为 $O(n)$ ，n 是数组 nums 的长度。
• 空间复杂度：只使用了常数级别的额外变量（maxReach、target、i ），空间复杂度为 $O(1)$ 。

二、LeetCode 45. 跳跃游戏 II——求最小跳跃次数

（一）题目剖析：最小跳跃次数的计算

给定非负整数数组 nums，初始位置为 nums[0] ，每个元素表示从该索引向后跳转的最大长度。要求返回到达 n - 1 位置（n 为数组长度 ）的最小跳跃次数，且题目保证可以到达终点。核心是在遍历中，合理维护跳跃边界，动态计算最小跳跃次数。

（二）算法思想：贪心算法的边界优化

依旧基于贪心算法，策略为：

• 维护关键变量：currentEnd 记录当前跳跃能到达的最远边界，farthest 记录目前遍历过程中能到达的最远位置，jumps 记录跳跃次数。
• 跳跃时机判断：遍历数组时，不断更新 farthest 。当遍历到 currentEnd 时，说明当前跳跃已到边界，必须进行下一次跳跃，此时更新 jumps 和 currentEnd（将 currentEnd 设为 farthest ）。通过这样的方式，每次在必须跳跃时才增加次数，保证跳跃次数最少，因为每次跳跃都尽可能覆盖更远的范围，这是贪心“每一步都选最优（覆盖最远 ）”的体现。

（三）代码实现与注释解析

class Solution {
    public int jump(int[] nums) {
        // 数组长度为 1 时，无需跳跃，直接返回 0
        if (nums.length <= 1) { 
            return 0; 
        }
        // 记录跳跃次数
        int jumps = 0; 
        // 当前跳跃能到达的最远边界
        int currentEnd = 0; 
        // 目前能到达的最远位置
        int farthest = 0; 
        // 遍历数组，因最后一个位置无需再跳跃（到达即结束），所以遍历到 nums.length - 2
        for (int i = 0; i < nums.length - 1; i++) { 
            // 更新能到达的最远位置，取之前的 farthest 和从当前位置 i 起跳能到的位置的最大值
            farthest = Math.max(farthest, i + nums[i]); 
            // 当到达当前跳跃的边界时，必须进行下一次跳跃
            if (i == currentEnd) { 
                jumps++; 
                currentEnd = farthest; // 更新下一次跳跃的边界为目前能到达的最远位置
                // 如果当前边界已覆盖终点，提前结束循环
                if (currentEnd >= nums.length - 1) { 
                    break; 
                }
            }
        }
        return jumps; 
    }
}

代码执行流程

1. 特殊情况处理：若数组长度 <= 1 ，无需跳跃，直接返回 0 。
2. 初始化变量：jumps 记录跳跃次数，初始为 0 ；currentEnd 初始为 0 ，代表初始跳跃（第 0 次跳跃 ）能到达的边界；farthest 初始为 0 ，用于记录遍历中能到达的最远位置。
3. 遍历数组：遍历到 nums.length - 2（因为到达倒数第二个位置后，下次跳跃就能到终点 ）：
   • 更新 farthest ，拓展能到达的最远范围。
   • 当 i == currentEnd 时，说明当前跳跃已到边界，需要进行下一次跳跃：
     • jumps 加 1 ，记录跳跃次数。
     • 更新 currentEnd 为 farthest ，确定下一次跳跃的边界。
     • 若 currentEnd >= nums.length - 1 ，说明已能到达终点，提前跳出循环。
4. 返回结果：循环结束后，jumps 即为到达终点的最小跳跃次数，返回该值。

（四）复杂度分析

• 时间复杂度：遍历一次数组，时间复杂度为 $O(n)$ ，n 是数组 nums 的长度。
• 空间复杂度：使用常数级别的额外变量（jumps、currentEnd、farthest、i ），空间复杂度为 $O(1)$ 。

三、两道题的对比与贪心思想总结

（一）对比分析

（二）贪心思想总结

这两道题均运用贪心算法，通过局部最优选择推导全局最优解：

• 55 题中，每一步尽可能拓展能到达的最远位置，一旦覆盖终点就提前结束，保证判断高效。
• 45 题中，在必须跳跃时（到达当前边界 ）才跳跃，且每次跳跃选择能覆盖最远的位置作为新边界，确保跳跃次数最少。

这种贪心策略，将复杂的跳跃问题拆解为简单的遍历与边界维护，大幅降低时间复杂度，体现了贪心算法“以小见大、步步最优”的魅力。