問(wèn)題描述：

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

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

示例：

示例 1：

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

示例 2：

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

思路分析：

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

解題關(guān)鍵點(diǎn)：

1. 當(dāng)前跳躍的最遠(yuǎn)距離：我們?cè)诒闅v數(shù)組時(shí)，每次計(jì)算當(dāng)前位置能夠跳躍到的最遠(yuǎn)位置，并更新最遠(yuǎn)位置。
2. 跳躍次數(shù)的增加：當(dāng)遍歷到當(dāng)前位置的最遠(yuǎn)位置時(shí)，說(shuō)明需要再進(jìn)行一次跳躍。跳躍的次數(shù)會(huì)增加。
3. 貪心選擇：每次選擇跳躍到當(dāng)前能到達(dá)的最遠(yuǎn)位置，從而確保跳躍次數(shù)最少。

代碼解析：

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

詳細(xì)講解：

1. 初始化變量：

   • ans: 記錄跳躍次數(shù)，初始為 0。
   • cur: 當(dāng)前跳躍的最遠(yuǎn)位置，初始為 0（從數(shù)組的第一個(gè)位置開(kāi)始）。
   • next: 下一跳能夠到達(dá)的最遠(yuǎn)位置，初始為 0。

2. 遍歷數(shù)組：

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

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

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

4. 最終結(jié)果：

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

例子解析：

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

1. 初始化：ans = 0, cur = 0, next = 0
2. 遍歷開(kāi)始：
   • 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. 遍歷開(kāi)始：
   • 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。

總結(jié)：

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

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