$$\color{Red}{跳跃游戏 II【leetcode44 贪心】}$$

下面的链接是——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

给定一个长度为 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:

输入: 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]

解析

这道题应该结合 55题的跳跃游戏 I 综合做，可以有更多的感悟，y总的方法，即使用递推 + 动态规划的思路，其实理解难度更大，而且很难观察出这道题的递增性质。

故这里采用我做完 55题 ，直觉上直接想使用双指针。

55题是判断能否跳到终点，故我们使用一个指针指向当前的最远能到达的位置，另一个指针遍历它之前的每个节点，然后不断更新最远能到达的位置在一个变量中，同时更新第一个指针即最远能到达的位置，相当于贪心的思想。一旦发现最远能到达的位置，已经大于等于终点位置，即成功。

这道题，显然我们不能完全使用之前的思路，之前的思路只考虑了能跳到哪，没有考虑步数，其实基于贪心的思想，我们还是可以考虑，枚举所有目前点能跳到的点的集合，如果其中一个点下一步跳的范围是集合中最远的，我们就选择下一步跳到这里。

即每步优先考虑能让未来跳的更远的点。

为什么 next 从 0 开始枚举？

因为可以把 nums.length == 1 的情况，即不跳，纳入考虑，不需要判边界，即开局就判断需不需要跳。

因为只有判断跳了，我们才能从当前点能跳到的集合中选择跳到哪。

即先判断需要跳，就进行 ans ++ ， 考虑范围扩大，即指针移动到 temp 。

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int next = 0, ans = 0, temp = 0;

        for (int i = 0; i <= next; i ++) {
            if (next >= n - 1) break;
            temp = Math.max(temp, i + nums[i]);
            if (i == next) {
                next = temp;
                ans ++;
            }
        }
        return ans;
    }
}