045 跳跃游戏 II

🔗 相关链接

跳跃游戏 II

📜 题目描述

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

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

• (0 \leq j \leq nums[i])
• (i + j < n)

🎯 目标

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[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

注意：题目保证可以到达 nums[n-1]。

💡 思路

和跳跃游戏思路类似，只不过维护一个是否可到达的数组改为维护一个到达此处需要的最少步数的数组。

💻 代码实现

public int jump(int[] nums) {
    if (nums.length == 1) {
        return 0;
    }
    int[] steps = new int[nums.length];
    Arrays.fill(steps, 10001);
    steps[0] = 0;
    for (int i = 0; i < nums.length; i++) {
        int range = nums[i];
        if (i + range >= nums.length - 1) {
            return steps[i] + 1;
        }
        for (int j = i + 1; j <= Math.min(i + range, nums.length - 1); j++) {
            if (steps[j] > steps[i] + 1) {
                steps[j] = steps[i] + 1;
            }
        }
    }
    return steps[nums.length - 1];
}