問題描述：

給定一個長度為 n 的 0 索引整數(shù)數(shù)組 nums，我們從數(shù)組的第一個元素 nums[0] 開始。每個元素 nums[i] 表示從索引 i 可以跳躍的最大長度，換句話說，從位置 i，你可以跳到位置 i + j，其中 0 <= j <= nums[i]，且 i + j < n。

目標是返回到達數(shù)組最后一個元素 nums[n - 1] 的 最小跳躍次數(shù)。

示例：

示例 1：

輸入: nums = [2,3,1,1,4]
輸出: 2
解釋: 跳到最后一個位置的最小跳躍數(shù)是 2。從下標為 0 跳到下標為 1 的位置，跳 1 步，然后跳 3 步到達數(shù)組的最后一個位置。

示例 2：

輸入: nums = [2,3,0,1,4]
輸出: 2

思路分析：

這道題目可以使用 貪心算法 來解決。我們可以理解為：每一步選擇跳躍到能夠到達的最遠位置，直到到達數(shù)組的最后一個元素。

解題關鍵點：

1. 當前跳躍的最遠距離：我們在遍歷數(shù)組時，每次計算當前位置能夠跳躍到的最遠位置，并更新最遠位置。
2. 跳躍次數(shù)的增加：當遍歷到當前位置的最遠位置時，說明需要再進行一次跳躍。跳躍的次數(shù)會增加。
3. 貪心選擇：每次選擇跳躍到當前能到達的最遠位置，從而確保跳躍次數(shù)最少。

代碼解析：

class Solution {public int jump(int[] nums) {int ans = 0;          // 跳躍次數(shù)int cur = 0;          // 當前跳躍范圍的最遠位置int next = 0;         // 下一跳能夠到達的最遠位置// 遍歷數(shù)組，直到倒數(shù)第二個元素（最后一個元素不需要再跳）for (int i = 0; i < nums.length - 1; i++) {next = Math.max(next, i + nums[i]);  // 更新下一跳能到達的最遠位置// 如果已經(jīng)到達當前跳躍范圍的最遠位置，則需要增加跳躍次數(shù)if (i == cur) {cur = next;  // 更新當前跳躍的最遠位置ans++;       // 跳躍次數(shù)增加}}return ans;  // 返回跳躍次數(shù)}
}

詳細講解：

1. 初始化變量：

   • ans: 記錄跳躍次數(shù)，初始為 0。
   • cur: 當前跳躍的最遠位置，初始為 0（從數(shù)組的第一個位置開始）。
   • next: 下一跳能夠到達的最遠位置，初始為 0。

2. 遍歷數(shù)組：

   • 我們遍歷數(shù)組的每個位置，計算從當前位置能跳到的最遠位置。
   • next = Math.max(next, i + nums[i]): i + nums[i] 表示從當前索引 i 能跳到的最遠位置，我們不斷更新 next 為當前能到達的最遠位置。

3. 判斷是否需要增加跳躍次數(shù)：

   • if (i == cur): 當我們遍歷到當前位置 i 時，如果 i 正好是當前跳躍的最遠位置（即 i == cur），說明我們已經(jīng)走到了當前跳躍的邊界，下一次需要跳躍。
   • cur = next: 更新當前跳躍的最遠位置為 next。
   • ans++: 跳躍次數(shù)增加。

4. 最終結果：

   • 遍歷完成后，ans 就是從 nums[0] 跳到 nums[n-1] 所需的最小跳躍次數(shù)。

例子解析：

例子 1：nums = [2, 3, 1, 1, 4]

1. 初始化：ans = 0, cur = 0, next = 0
2. 遍歷開始：
   • i = 0：從位置 0 可以跳到 0 + nums[0] = 0 + 2 = 2，所以 next = 2。
   • i == cur (i == 0)：更新 cur = 2，跳躍次數(shù) ans = 1。
   • i = 1：從位置 1 可以跳到 1 + nums[1] = 1 + 3 = 4，所以 next = 4。
   • i == cur (i == 2)：更新 cur = 4，跳躍次數(shù) ans = 2。
   • 跳到最后，跳躍次數(shù)為 2。

例子 2：nums = [2, 3, 0, 1, 4]

1. 初始化：ans = 0, cur = 0, next = 0
2. 遍歷開始：
   • i = 0：從位置 0 可以跳到 0 + nums[0] = 0 + 2 = 2，所以 next = 2。
   • i == cur (i == 0)：更新 cur = 2，跳躍次數(shù) ans = 1。
   • i = 1：從位置 1 可以跳到 1 + nums[1] = 1 + 3 = 4，所以 next = 4。
   • i == cur (i == 2)：更新 cur = 4，跳躍次數(shù) ans = 2。
   • 跳到最后，跳躍次數(shù)為 2。

總結：

• 貪心思想：每次選擇跳躍到當前能到達的最遠位置，從而保證跳躍次數(shù)最少。
• 時間復雜度：O(n)，其中 n 是數(shù)組的長度。我們只遍歷了一次數(shù)組。
• 空間復雜度：O(1)，只使用了常數(shù)空間。

這就是 跳躍游戲 II 的貪心算法解法！