LeetCode 45. 跳跃游戏 II [Hot 100] —— 贪心

45. 跳跃游戏 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

class Solution {
    public int jump(int[] nums) {
        int cnt = 0;
        int curRight = 0;
        int nextRight = 0;
        for (int i = 0; i < nums.length - 1; i++) { // 维护
            nextRight = Math.max(nextRight, i + nums[i]); // 维护下一个最远值
            if (i == curRight) { // 到达现在最远值，跳
                cnt++;
                curRight = nextRight;
                if (curRight >= nums.length -1) break;
            }
        }
        return cnt;
    }
}

因为到达最后一个位置就不需要再跳了，所以循环条件是 i < nums.length - 1

贪心（BFS 思想）

我们可以用贪心在 O(n) 时间内解决。

思路：

• 维护当前能到达的最远位置 maxPos，以及当前跳跃的边界 end。
• 遍历数组，更新 maxPos。
• 当遍历到当前边界 end 时，表示必须再跳一次，此时更新 end 为 maxPos，跳跃次数 +1。

算法步骤

1. 初始化：

   • jumps = 0（跳跃次数）
   • maxPos = 0（当前能到达的最远位置）
   • end = 0（当前跳跃能到达的边界）

2. 遍历 i 从 0 到 n-2（因为到达最后一个位置后不需要再跳）：

   • 更新 maxPos = max(maxPos, i + nums[i])

   • 如果 i == end：

     • jumps++
     • end = maxPos
     • 如果 end >= n-1 可以提前结束
3. 返回 jumps