LeetCode 55 Jump Game：貪心算法 O(n) 判斷能否到達終點

題目描述

給定非負整數數組，初始位於索引 0。每個元素代表該位置最大跳躍長度。判斷能否到達最後一個下標。

示例：[2,3,1,1,4] → true；[3,2,1,0,4] → false。

貪心核心思想：維護「當前能到達的最遠位置」

遍歷數組，維護變量 maxReach 表示截至當前位置能到達的最遠下標：

• 初始 maxReach = 0
• 對於索引 i，若 i > maxReach → 無法到達 i，直接返回 false
• 更新 maxReach = max(maxReach, i + nums[i])
• 若循環中 maxReach >= n-1 → 可到達終點，返回 true

此法保證每個位置只訪問一次，O(n) 時間，O(1) 空間。

C++ 實現

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 true; // n==0 或循環結束均可達
    }
};

另一種視角：倒序貪心（從終點反推）

bool canJump(vector& nums) {
    int lastPos = nums.size() - 1;
    for (int i = nums.size() - 2; i >= 0; --i) {
        if (i + nums[i] >= lastPos) lastPos = i;
    }
    return lastPos == 0;
}

思路：從倒數第二個位置反推，若當前位置能跳到 lastPos，則更新 lastPos 為當前位置。最終若 lastPos==0 則可從起點到達。

關鍵點對比

常見錯誤避坑

• ❌ 用 DP O(n²) 或 BFS 會 TLE
• ❌ 忽略 i > maxReach 的不可達判斷（如 [0,1]）
• ❌ 更新 maxReach 前檢查導致邏輯錯誤

變體擴展：Jump Game II（最小跳躍次數）

同樣貪心，維護「當前步數能到達的最遠」與「下一步能到達的最遠」，步數+1 當遍歷超過當前最遠時。

總結

Jump Game 是貪心算法「維護可行邊界」的經典例題。正序維護 maxReach 既直觀又支持早退出；倒序反推 lastPos 代碼極簡。核心洞察：**局部最優（每步跳最遠）推導全局最優（能否到達終點）**，此思想廣泛適用於區間覆蓋、加油站、視頻拼接等問題。