Problem: 45. 跳躍游戲 II
給定一個長度為 n 的 0 索引整數數組 nums。初始位置為 nums[0]。
每個元素 nums[i] 表示從索引 i 向后跳轉的最大長度。換句話說，如果你在索引 i 處，你可以跳轉到任意 (i + j) 處：
0 <= j <= nums[i] 且
i + j < n
返回到達 n - 1 的最小跳躍次數。測試用例保證可以到達 n - 1。

整體思路

這段代碼旨在解決經典的 “跳躍游戲 II” (Jump Game II) 問題。與判斷“能否到達”的第一代問題不同，此問題要求在假設總能到達終點的前提下，計算出到達數組最后一個位置所需的 最小跳躍次數。

該算法采用了一種非常高效的 貪心算法，其思想可以類比為 廣度優先搜索 (BFS)。它不是關注每一步具體跳到哪里，而是在每一“跳”的范圍內，尋找下一“跳”能到達的最遠距離。

算法的邏輯步驟如下：

1. 定義邊界：

   • 算法使用兩個核心變量來定義跳躍的邊界：
     • curRight：當前這一跳所能到達的最遠邊界。可以理解為 BFS 中當前層的右邊界。
     • nxtRight：從當前層（0 到 curRight 之間的所有位置）出發，下一跳所能到達的最遠邊界。
   • ans 變量用于累計跳躍的次數。

2. 貪心遍歷：

   • 算法通過一個 for 循環遍歷數組。循環的終止條件是 i < nums.length - 1，這一點非常關鍵，因為我們只需要考慮從倒數第二個位置（或之前）起跳的情況，一旦到達或越過最后一個位置，就不需要再跳了。
   • 在當前跳躍范圍內尋找最優的下一步：在循環的每一步（i 從 0 到 curRight），我們都在當前可達的范圍內。對于每個位置 i，我們計算從它出發能跳到的最遠距離 nums[i] + i。然后，我們用這個值去貪心地更新 nxtRight (nxtRight = Math.max(nxtRight, nums[i] + i))。這確保了 nxtRight 始終記錄著從當前這一跳的覆蓋范圍內，能為下一跳創造的最遠落點。
   • 執行跳躍：當循環變量 i 到達了 curRight 的邊界時，意味著我們已經遍歷完了當前這一跳能到達的所有位置。此時，我們必須執行一次跳躍才能繼續前進。
     • if (i == curRight) 這個條件就是“執行跳躍”的觸發器。
     • 當觸發時，我們將 curRight 更新為 nxtRight，這相當于進入了 BFS 的下一層，設定了新的、更遠的可達邊界。
     • 同時，我們將跳躍次數 ans 加一。

3. 返回結果：

   • 當循環結束時，ans 中就記錄了到達終點所需的最小跳躍次數。

完整代碼

class Solution {/*** 計算到達數組最后一個位置所需的最小跳躍次數。* @param nums 數組，每個元素代表在該位置的最大跳躍長度。* @return 最小跳躍次數*/public int jump(int[] nums) {// curRight: 當前這一跳能夠到達的最遠右邊界。int curRight = 0;// nxtRight: 在當前跳躍的覆蓋范圍內，下一步能夠到達的最遠右邊界。int nxtRight = 0;// ans: 記錄跳躍的次數，即結果。int ans = 0;// 遍歷數組。循環到倒數第二個元素即可，因為我們的目標是“到達”最后一個位置，// 而不是從最后一個位置起跳。for (int i = 0; i < nums.length - 1; i++) {// 貪心選擇：更新下一步能到達的最遠距離。// 在當前跳躍的可達范圍內（i 從 0 到 curRight），// 我們不斷計算從每個位置 i 出發能跳到的最遠點 (nums[i] + i)，// 并用它來更新 nxtRight。nxtRight = Math.max(nxtRight, nums[i] + i);// 觸發跳躍的條件：當 i 到達了當前跳躍的邊界。// 這意味著我們已經考察完了當前這一跳能到達的所有位置，// 必須進行一次新的跳躍才能繼續前進。if (i == curRight) {// 更新當前跳躍的邊界為下一步能到達的最遠邊界。curRight = nxtRight;// 跳躍次數加一。ans++;}}// 循環結束后，ans 即為最小跳躍次數。return ans;}
}

時空復雜度

時間復雜度：O(N)

1. 循環：算法的核心是一個 for 循環，它從 i = 0 遍歷到 nums.length - 2。這個循環最多執行 N-1 次，其中 N 是 nums 數組的長度。
2. 循環內部操作：
   • 在循環的每一次迭代中，執行的都是基本的 Math.max、加法、比較和賦值操作。
   • 這些操作的時間復雜度都是 O(1)。

綜合分析：
算法由 N-1 次 O(1) 的操作組成。因此，總的時間復雜度是 (N-1) * O(1) = O(N)。

空間復雜度：O(1)

1. 主要存儲開銷：算法只使用了幾個固定數量的整型變量（curRight, nxtRight, ans, i）。
2. 空間大小：這些變量的數量不隨輸入數組 nums 的大小 N 而改變。

綜合分析：
算法沒有使用任何與輸入規模 N 成比例的額外數據結構（如新數組或哈希表）。因此，其額外輔助空間復雜度為 O(1)。

參考靈神