LeetCode-45. 跳躍游戲II - 題解分析

題目來源

45. 跳躍游戲 II

題目詳情

給定一個長度為 n 的 0 索引整數數組 nums。初始位置為 nums[0]。

每個元素 nums[i] 表示從索引 i 向前跳轉的最大長度。換句話說，如果你在 nums[i] 處，你可以跳轉到任意 nums[i + j] 處:

• 0 <= j <= nums[i]
• i + j < n

返回到達 nums[n - 1] 的最小跳躍次數。生成的測試用例可以到達 nums[n - 1]。

示例 1:

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

示例 2:

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

提示:

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 1000
• 題目保證可以到達 nums[n-1]

相似題目

55. 跳躍游戲

題解分析

本題與[55. 跳躍游戲]這題不同，不能使用相同的貪心思路來解決。這裡需要求解的問題是最小的跳躍次數，而要求解最小的跳躍次數需要每次在跳躍時選擇儘可能跨度大的格子。

換句話說，只需要判斷哪一個選擇最具有「潛力」即可：

比如上圖這種情況，我們站在索引 0 的位置，可以向前跳 1，2 或 3 步，你說應該選擇跳多少呢？

顯然應該跳 2 步調到索引 2，因為 nums[2] 的可跳躍區域涵蓋了索引區間 [3..6]，比其他的都大。如果想求最少的跳躍次數，那麼往索引 2 跳必然是最優的選擇。

你看，這就是貪心選擇性質，我們不需要「遞歸地」計算出所有選擇的具體結果然後比較求最值，而只需要做出那個最有「潛力」，看起來最優的選擇即可。

i 和 end 標記了可以選擇的跳躍步數，farthest 標記了所有選擇 [i..end] 中能夠跳到的最遠距離，jumps 記錄了跳躍次數。

本演算法的時間複雜度 O(N)，空間複雜度 O(1)。

java實現

class Solution {
    public int jump(int[] nums) {
        int right = 0, maxStep = 0, len = nums.length;
        int steps = 0;
        for (int i=0; i<len-1; i++) {
            maxStep = Math.max(maxStep, nums[i] + i);
            if (i == right) {
                right = maxStep;
                steps++;
            }
        }
        return steps;
    }
}

參考

如何運用貪心思想玩跳躍游戲