給定一個長度為 n 的 0 索引整數(shù)數(shù)組 nums。初始位置為 nums[0]。
每個元素 nums[i] 表示從索引 i 向前跳轉(zhuǎn)的最大長度。換句話說，如果你在 nums[i] 處，你可以跳轉(zhuǎn)到任意 nums[i + j] 處:
● 0 <= j <= nums[i]
● i + j < n
返回到達(dá) nums[n - 1] 的最小跳躍次數(shù)step。生成的測試用例可以到達(dá) nums[n - 1]。

解題思路：
本題和55. 跳躍游戲的區(qū)別在于：55只需要判斷是否能到達(dá)最后一個位置，不在意需要跳多少次。
而本題需要跳躍次數(shù)盡可能小，也就是說關(guān)鍵點(diǎn)在于如何定義跳躍一次。

其實(shí)思路和55.差不多，我們?nèi)匀恍枰澬呢澰诒M可能大的右界，只是我們并不是每遍歷一個元素就更新最大右界，因?yàn)槲覀冎辽僖袛嗤辍井?dāng)前這個覆蓋區(qū)間是否能到達(dá)最后一個位置】，如果都不能了，那么說明我們需要繼續(xù)在這個覆蓋區(qū)間遍歷判斷。我們定義【step：到達(dá)遍歷的指針 i 所需要的最少跳躍次數(shù)】。

● 因此跳躍次數(shù)累加應(yīng)該在遍歷指針 i 到達(dá)了本次的最大右界，且仍然不能覆蓋最后一個位置。
累加完成后，更新下一個最大右界（遍歷的過程應(yīng)該記錄）

? 注意細(xì)節(jié)：
(1) 初始化。初始化最大右界應(yīng)該為0，step=0，i=0。數(shù)組可能只有一個元素，最開始的元素需判斷： i == nums.length - 1（在判斷覆蓋區(qū)間前，因?yàn)橐坏┻M(jìn)入了覆蓋區(qū)間是否覆蓋了最后一個元素的邏輯，就說明指針 i 要進(jìn)行至少一跳，但有可能本身指針 i 所指向的就是最后一個元素）。
(2) 判斷 i 的右界是否已經(jīng)覆蓋了最后一個位置，如果是，需要返回step + 1（ i 要跳躍一次才能到達(dá)覆蓋區(qū)間）。且這個判斷要在【i == 本次最大右界】（說明本次覆蓋區(qū)間不能覆蓋到最后一個位置）之前。

class Solution {
    public int jump(int[] nums) {
        int i = 0; // 當(dāng)前覆蓋區(qū)域中的某一個元素
        int cur_max_index = 0; // 當(dāng)前（不是指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; // 該元素的覆蓋區(qū)域包括了最后一個位置
            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){ // 當(dāng)前跳數(shù)輪次已經(jīng)查過，都到不了目的地
                cur_max_index = next_max_index;
                next_max_index = 0;
                hop++; // 必須再跳一次
            }
        }
        return hop+1;
    }
}