贪心算法求解最小跳跃次数（LeetCode 45）

---

题目描述

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 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

提示:

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 1000
• 题目保证可以到达 n - 1

贪心算法

核心思路

1. 初始化三个变量：
   • max：记录当前能够到达的最远位置
   • end：记录当前跳跃能够到达的边界，到达边界时，步数需要加 1，并且更新边界为当前能够到达的最远位置 max
   • step：记录跳跃的步数
2. 遍历数组：
   • 更新当前能够到达的最远位置
   • 当遍历到当前边界时，意味着这一步已经无法再继续前进，须进行一次跳跃，更新边界为当前能够到达的最远位置，并增加跳跃次数
   • 注意不需要遍历最后一个元素，因为当到达最后一个元素时不需要再跳跃
3. 返回跳跃次数

代码实现

public int jump(int[] nums) {
    // 处理边界情况：数组为空或长度为0
    if (nums == null || nums.length == 0) {
        return 0;
    }
    
    int max = 0;    // 记录当前能够到达的最远位置
    int end = 0;    // 记录当前跳跃能够到达的边界
    int step = 0;   // 记录跳跃次数
    
    // 遍历数组，注意不需要遍历最后一个元素
    for (int i = 0; i < nums.length - 1; i++) {
        // 更新当前能够到达的最远位置
        if (i + nums[i] > max) {
            max = i + nums[i];
        }
        
        // 当遍历到当前边界时，必须进行一次跳跃
        if (i == end) {
            step++;     // 增加跳跃次数
            end = max;  // 更新边界为当前能够到达的最远位置
        }
    }
    
    return step;
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度。我们只需要遍历数组一次。
• 空间复杂度：O(1)，只使用了常数级别的额外空间。

总结

本题使用贪心算法，通过维护当前能够到达的最远位置和当前跳跃的边界，确保了每次跳跃都是最优选择，从而得到最少的跳跃次数。算法的时间复杂度为线性，空间复杂度为常数，是非常高效的解决方案。

来源

45. 跳跃游戏 II | 力扣（LeetCode）
45. 跳跃游戏 II | 题解 | 灵茶山艾府

---