045-跳跃游戏 II

给定一个长度为 n 的 0 索引整数数组 nums 。初始位置在下标 0。

每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处：

• 0 <= j <= nums[i] 且
• i + j < n

返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1。

示例 1：

输入：nums = [2,3,1,1,4]
输出：2
解释：跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2：

输入：nums = [2,3,0,1,4]
输出：2

思路：贪心算法（边界控制）

核心思想：把跳跃过程看成「层」的遍历，每一跳代表一层。

• 维护三个变量：

  • steps：跳跃步数
  • end：当前这一跳能到达的最远边界（当前层的右边界）
  • nextEnd：下一跳能到达的最远边界（下一层的右边界）

• 遍历数组（注意只需要遍历到 n-2，因为到最后一个位置就结束了）：

  • 对于每个位置 i，更新 nextEnd = Math.max(nextEnd, i + nums[i])
  • 当 i == end 时，说明当前层已经遍历完，必须再跳一步：
    • steps++
    • end = nextEnd（进入下一层）
    • 如果 nextEnd >= n-1，说明已经能到达终点，提前退出

代码实现

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        if (n <= 1) return 0;
        
        // 跳跃步数
        int steps = 0;
        // 当前一跳的最远边界
        int end = 0;
        // 下一跳的最远边界
        int nextEnd = 0;

        for (int i = 0; i < n - 1; i++) {
            // 1) 扫描当前层内的每个位置 i
            // 从 i 出发最多跳到 i + nums[i]，不断更新"下一层"能达到的最远边界 nextEnd
            nextEnd = Math.max(nextEnd, i + nums[i]);

            // 2) 当 i 走到当前层的右边界 end，说明：
            // - 在 steps 次跳跃内能到达的所有点都已经扫描完了（当前层结束）
            // - 如果还没覆盖到终点，就必须再跳一次进入下一层
            if (i == end) {
                steps++;
                end = nextEnd;
                // 跳完以后立马判断是否可以退出了
                if (nextEnd >= n - 1) {
                    break;
                }
            }
        }

        return steps;
    }
}

复杂度分析

• 时间复杂度：O(n)，只需遍历一次数组。
• 空间复杂度：O(1)，只使用了常数额外空间。

与「跳跃游戏 I」的区别

跳跃游戏 II 在 I 的基础上增加了「步数计数」，需要更精细地控制每一跳的边界。