45 跳跃游戏 II

一、题目

45. 跳跃游戏 II

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

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

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

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


二、题解

2.1 贪心

核心思想：

把每一次跳跃看成一个「范围」。

例如当前这一跳可以覆盖到下标 currentEnd，在这个范围内，我们不断更新下一跳能到达的最远位置 farthest。

当遍历到 currentEnd 时，说明当前这一步的范围用完了，必须再跳一次。

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;

        if (n <= 1) {
            return 0;
        }

        int steps = 0;       // 跳跃次数
        int currentEnd = 0;  // 当前这一步能到达的最远位置
        int farthest = 0;    // 下一步能到达的最远位置

        for (int i = 0; i < n - 1; i++) {
            // 在当前可达范围内，更新下一跳能到达的最远位置
            farthest = Math.max(farthest, i + nums[i]);

            // 到达当前这一步的边界，必须跳一次
            if (i == currentEnd) {
                steps++;
                currentEnd = farthest;

                // 已经可以到达或超过终点
                if (currentEnd >= n - 1) {
                    break;
                }
            }
        }

        return steps;
    }
}

时间复杂度：$O(n)$

空间复杂度：$O(1)$

2.2 动态规划

dp[i] 表示到达下标 i 的最少跳跃次数，对于每个位置 i，看前面的某个位置 j 能不能跳到 i。

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];

        for (int i = 1; i < n; i++) {
            dp[i] = Integer.MAX_VALUE;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= nums[i] && i + j < n; j++) {
                dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
            }
        }

        return dp[n - 1];
    }
}

时间复杂度：$O(n^2)$

空间复杂度：$O(n)$