给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
● 0 <= j <= nums[i]
● i + j < n
返回到达 nums[n - 1] 的最小跳跃次数step。生成的测试用例可以到达 nums[n - 1]。
解题思路：
本题和55. 跳跃游戏的区别在于：55只需要判断是否能到达最后一个位置，不在意需要跳多少次。
而本题需要跳跃次数尽可能小，也就是说关键点在于如何定义跳跃一次。
其实思路和55.差不多，我们仍然需要贪心贪在尽可能大的右界，只是我们并不是每遍历一个元素就更新最大右界，因为我们至少要判断完【当前这个覆盖区间是否能到达最后一个位置】，如果都不能了，那么说明我们需要继续在这个覆盖区间遍历判断。我们定义【step：到达遍历的指针 i 所需要的最少跳跃次数】。
● 因此跳跃次数累加应该在遍历指针 i 到达了本次的最大右界，且仍然不能覆盖最后一个位置。
累加完成后，更新下一个最大右界（遍历的过程应该记录）
⭕ 注意细节：
(1) 初始化。初始化最大右界应该为0，step=0，i=0。数组可能只有一个元素，最开始的元素需判断： i == nums.length - 1（在判断覆盖区间前，因为一旦进入了覆盖区间是否覆盖了最后一个元素的逻辑，就说明指针 i 要进行至少一跳，但有可能本身指针 i 所指向的就是最后一个元素）。
(2) 判断 i 的右界是否已经覆盖了最后一个位置，如果是，需要返回step + 1（ i 要跳跃一次才能到达覆盖区间）。且这个判断要在【i == 本次最大右界】（说明本次覆盖区间不能覆盖到最后一个位置）之前。
class Solution {
public int jump(int[] nums) {
int i = 0; // 当前覆盖区域中的某一个元素
int cur_max_index = 0; // 当前（不是指i）覆盖的最大右边界
int next_max_index = cur_max_index; // 下一次覆盖的最大右边界
int step = 0;
while(i < nums.length){
if(i == nums.length - 1) return step; // 防止1个元素的情况
int tmp = i + nums[i];
// if(i == 0) cur_max_index = nums[i];
if(tmp >= nums.length - 1) return ++step; // 该元素的覆盖区域包括了最后一个位置
if(tmp > next_max_index) next_max_index = tmp; // 更新下一个最大覆盖右边界，此时不可能包括最后一个位置
if(i == cur_max_index){
step++;
cur_max_index = next_max_index;
}
i++;
}
return step;
}
}
Java-2023
class Solution {
public int jump(int[] nums) {
if(nums.length == 1) return 0;
int hop = 0;
int cur_max_index = 0;
int next_max_index = 0;
for(int i=0; i<nums.length; i++){
int tmp = nums[i] + i;
if(tmp >= nums.length-1) break;
if(tmp > next_max_index) next_max_index = tmp;
if(i == cur_max_index){ // 当前跳数轮次已经查过，都到不了目的地
cur_max_index = next_max_index;
next_max_index = 0;
hop++; // 必须再跳一次
}
}
return hop+1;
}
}
