45. 跳跃游戏 II

📝 题目描述

给定一个长度为 n 的非负整数数组 nums，初始位置在下标 0。每个元素 nums[i] 表示从索引 i 向后跳的最大长度（即在 i 处可跳到 i+j，其中 0 ≤ j ≤ nums[i] 且 i+j < n）。返回到达 n-1 的最小跳跃次数（题目保证可以到达终点）。

---

📌 示例

示例 1

输入：

nums = [2,3,1,1,4]

输出：

2

解释：从下标 0 跳到 1（跳 1 步），再从 1 跳 3 步到终点，共 2 次跳跃。

示例 2

输入：

nums = [2,3,0,1,4]

输出：

2

---

🚀 最优解：贪心算法（跟踪边界与最远可达）

🔍 思路解析

核心贪心策略：每一轮跳跃都覆盖当前能到达的最远范围，到达当前范围边界时必须跳一次，保证跳跃次数最少。

1. 初始化变量：
   • ans：记录最少跳跃次数；
   • end：当前轮次跳跃的最远边界；
   • curEnd：遍历过程中能到达的全局最远索引；
2. 遍历数组（到倒数第二个元素即可，到达终点无需再跳）：
   • 持续更新 curEnd 为 max(curEnd, i + nums[i])（当前位置能跳到的最远索引）；
   • 当遍历到 end（当前轮次的边界）时，跳一次（ans++），并将 end 更新为 curEnd；
   • 若 end 已覆盖终点，提前终止循环。

---

✅ 完整代码（Java）

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Read the array
        String input = scanner.nextLine();
        input = input.substring(1, input.length() - 1); // Remove brackets
        String[] numsStr = input.split(",");

        int[] nums = new int[numsStr.length];
        for (int i = 0; i < numsStr.length; i++) {
            nums[i] = Integer.parseInt(numsStr[i].trim());
        }

        Solution solution = new Solution();
        int result = solution.jump(nums);

        System.out.println(result);
        scanner.close();
    }
}

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        // 边界：只有一个元素，无需跳跃
        if (n == 1) return 0;

        int ans = 0;        // 最少跳跃次数
        int end = 0;        // 当前轮次的跳跃边界
        int curEnd = 0;     // 全局最远可达索引

        for (int i = 0; i < n - 1; i++) {
            // 更新全局最远可达索引
            curEnd = Math.max(curEnd, i + nums[i]);

            // 到达当前轮次的边界，必须跳一次
            if (i == end) {
                ans++;
                end = curEnd; // 更新下一轮的边界

                // 提前终止：已能到达终点
                if (end >= n - 1) break;
            }
        }
        return ans;
    }
}

---

🧠 通俗易懂解释

可以把问题理解为“分批跳，每批跳最远”：

• 第1批：从起点0出发，能跳到的范围是0~nums[0]，这一批的最远边界是end；
• 遍历这一批的所有位置，记录“这一批里能跳到的最远位置”（curEnd）；
• 当走完这一批（到达end），必须跳一次，进入下一批（下一批的范围是end+1~curEnd）；
• 重复此过程，直到覆盖终点。

以示例1 nums = [2,3,1,1,4] 为例：

1. 第1批：起点0，范围0~2，遍历中curEnd更新为0+2=2、1+3=4、2+1=3，最终curEnd=4；
2. 到达end=2，跳一次（ans=1），下一批边界更新为4；
3. 第2批：范围3~4，但end=4已覆盖终点4，提前终止，最终跳跃次数为2。

---

⏱ 时间复杂度

O(n)

仅遍历数组一次（到倒数第二个元素），每个元素的计算为常数时间，效率最优。

---

💾 空间复杂度

O(1)

仅使用ans、end、curEnd三个变量，无额外空间消耗。