LeetCode 55 Jump Game：貪心判斷能否到達終點

題目大意

數組 nums，每個元素代表在該位置**最大**跳躍長度。初始在位置 0，判斷能否到達最後一個下標。

貪心核心：維護最遠可達位置

• 遍歷數組，維護 `maxReach` = 目前能到達的最遠下標。
• 對位置 i，若 `i > maxReach` 則無法到達 i，直接返回 false。
• 否則更新 `maxReach = max(maxReach, i + nums[i])`。
• 若循環結束 `maxReach >= n-1` 返回 true。

代碼

class Solution {
public:
    bool canJump(vector& nums) {
        int maxReach = 0;
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            if (i > maxReach) return false;
            maxReach = max(maxReach, i + nums[i]);
            if (maxReach >= n-1) return true; // 提前結束
        }
        return maxReach >= n-1;
    }
};

為什麼貪心正確？

若位置 i 可達，則 [0, i] 所有位置均可達（因可從更早位置跳過）。`maxReach` 記錄所有可達位置能延伸的最遠邊界。若某位置 i 超出此邊界，說明無路可達 i，後續更遠位置也不可達。

複雜度

• 時間：O(n)，單次遍歷。
• 空間：O(1)。

總結

Jump Game 是貪心算法的教科書級例題。**維護最遠可達邊界** 替代了 DP 或 BFS，將 O(n²) 或 O(n) 空間優化為 O(n) 時間 O(1) 空間。關鍵洞見：可達區間總是連續的 [0, maxReach]。