跳转至

45. 跳跃游戏 II

力扣链接(中等)：https://leetcode.cn/problems/jump-game-ii

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

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

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

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1:

Text Only
1
2
3
4
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:

Text Only
1
2
输入: nums = [2,3,0,1,4]
输出: 2

提示:

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

个人题解

这道题我仍然需要解释一下，不然 99% 的脑壳没办法一眼看出来以下题解是在做什么。

在枚举过程中，每走到一个位置，就会获取当前位置的最大跳跃能力，本题需要求解最小跳跃次数，所以显然是不能乱跳的，也不能每次无脑跳最大长度，这样可能会错过下一次更大的跳跃长度。

那么每次跳跃都需要合理选择跳跃的位置，nextCover 用于记录下一次跳跃能到达的最大距离，从而选择出当前 cover 包含位置中最合理的一个跳跃位置，使得下一次跳跃覆盖的范围最大。

例如 [2, 3, 0, 1]，第一步可以最大跳 2 个距离，但你会发现，如果无脑跳最大距离 2，会导致下一次无法继续跳跃了，总的跳跃长度为 2 且未到达终点，直接 Mission Failed，那我要是选择跳 1 个距离，那么我后续就可以跳 1 + 3 = 4 个距离，且到达了终点。

C++
1
nextCover = max(nums[i] + i, nextCover)

i == cover 时，代表当前 cover 包含的位置已经枚举完成，已经迭代出了最大的 nextCover ，将 cover = nextCover 代表这次跳到了最合适的位置，找到了局部最优解（当前可移动距离尽可能大）。进一步的，就可以找到整体最优解。

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int jump(vector<int>& nums) {
        if(nums.size() == 1) return 0;

        int result = 0;
        // 当前跳跃能覆盖的位置
        int cover = 0;
        // 下一步跳跃的最大覆盖位置
        int nextCover = 0;

        for(int i = 0; i < nums.size(); i++) {
            nextCover = max(nums[i] + i, nextCover);
            if(i == cover) {
                result++;
                // 跳到最合理的位置
                cover = nextCover;
                // 到达终点
                if(cover >= nums.size() - 1) break;
            }
        }

        return result;
    }
};