LeetCode 45：Jump Game II —— 貪心算法優化詳解

題目

給定非負整數數組，初始位於索引 0。每個元素代表該位置最大跳躍長度。求到達最後一個索引的最小跳躍次數。

範例

輸入: [2,3,1,1,4]
輸出: 2
解釋: 0→1 (跳 1 步), 1→4 (跳 3 步)

三種解法演進

1. DP + 前驅記錄 → TLE

d[i] = 從 0 到 i 最小步數，d[i] = min(d[k]+1) 其中 k 能到達 i。記錄所有前驅導致 O(n²) 空間與時間，超時。

2. DP 優化空間 → 仍 TLE

只保留 d[] 不存前驅，空間 O(n)，但時間仍 O(n²)，大數據超時。

3. 貪心算法（最優）— O(n) 時間，O(1) 空間

核心思想：維護「第 k 步能到達的最遠範圍 [left, right]」。

• 初始 left = right = 0，步數 step = 0。
• 當前範圍 [left, right] 內，尋找下一步能到達的最遠位置 mostRight。
• 若 mostRight ≥ n-1，step+1 即為答案。
• 否則 left = right + 1，right = mostRight，step++，繼續。

關鍵優化：left 直接跳到 right+1，而非 left+1，因為 [left+1, right] 已在上一輪掃描過，避免重複計算。

貪心代碼（C++）

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) return 0;
        int left = 0, right = 0, step = 0;
        while (right < n - 1) {
            int mostRight = 0;
            for (int i = left; i <= right; ++i)
                mostRight = max(mostRight, i + nums[i]);
            if (mostRight >= n - 1) return step + 1;
            left = right + 1;
            right = mostRight;
            ++step;
            if (right < left) return -1; // 不可達（題目保證可達）
        }
        return step;
    }
};

複雜度對比

直觀理解

把跳躍看作「層次擴展」：第 0 層只有索引 0；第 1 層是從第 0 層任意點一步能到的所有點；第 2 層是從第 1 層任意點一步能到的所有點……第一次擴展到終點時的層數即為答案。貪心算法正是在模擬這個 BFS 過程，但只記錄每層的邊界 [left, right]，不顯式存儲節點。