Leetcode 45.跳跃游戏 II

力扣传送门(opens new window)

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

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

说明: 假设你总是可以到达数组的最后一个位置。

解题思路：

如果某一个作为 起跳点 的格子可以跳跃的距离是 3，那么表示后面 3 个格子都可以作为 起跳点。
可以对每一个能作为 起跳点 的格子都尝试跳一次，把 能跳到最远的距离 不断更新。

如果从这个 起跳点 起跳叫做第 1 次 跳跃，那么从后面 3 个格子起跳 都 可以叫做第 2 次 跳跃。

所以，当一次 跳跃 结束时，从下一个格子开始，到现在 能跳到最远的距离，都 是下一次 跳跃 的 起跳点。
对每一次 跳跃 用 for 循环来模拟。

跳完一次之后，更新下一次 起跳点 的范围。
在新的范围内跳，更新 能跳到最远的距离。
记录 跳跃 次数，如果跳到了终点，就得到了结果。

图解

代码实现：

public class Solution {
    public int jump(int[] nums) {
        int ans = 0;
        int start = 0;
        int end = 1;
  
        while (end < nums.length) {
            int maxPos = 0;
            for (int i = start; i < end; i++) {
                maxPos = Math.max(maxPos, i + nums[i]);
            }
            start = end;
            end = maxPos + 1;
            ans++;
        }
  
        return ans;
    }
}

在这段代码中，start初始值为0， end 的初始值为 1，是因为我们这里是用了双指针，来代表start到end距离是当前覆盖的范围。然后我们使用这段距离来进行遍历，来得到下一次能够覆盖到的最大距离。以此来更新maxPos，找到下一次覆盖的最大距离之后，我们把start和end相继更新。并且记录一次跳跃，即 ans++。

优化

从上面代码观察发现，其实被 while 包含的 for 循环中，i 是从头跑到尾的。

只需要在一次 跳跃 完成时，更新下一次 能跳到最远的距离。

并以此刻作为时机来更新 跳跃 次数。

就可以在一次 for 循环中处理。

public class Solution {
    public int jump(int[] nums) {
        int ans = 0;
        int end = 0;
        int maxPos = 0;
  
        for (int i = 0; i < nums.length - 1; i++) {
            maxPos = Math.max(nums[i] + i, maxPos);
            if (i == end) {
                end = maxPos;
                ans++;
            }
        }
  
        return ans;
    }
}

这里其实应该有个疑问，为什么循环的条件是nums.length-1呢？

其实 循环的条件 i < nums.length - 1 是因为在每次循环中，我们检查当前位置 i 是否到达了当前跳跃范围 end。也就是我们每次循环都要判断是否最大的覆盖范围是否到达最后一个位置。

如果 i 等于 nums.length - 1，意味着当前位置已经是数组的最后一个位置，不需要再进行跳跃。假如说我们跳跃到了倒数第二个位置，那么我们就不需要循环了，因为此时result已经++了，因此，我们将循环条件设置为 i < nums.length - 1，以保证在到达最后一个位置之前继续循环。

当循环结束时，我们已经计算出了到达最后一个位置所需的最小跳跃次数。