55. Jump Game

題目 / Problem

中文： 給定一個整數陣列 nums。你最初位於陣列的第一個索引，陣列中的每個元素代表你在該位置可以跳躍的最大長度。

如果可以到達最後一個索引，回傳 true；否則回傳 false。

English: You are given an integer array nums. You start at the first index, and each element represents the maximum jump length from that position.

Return true if you can reach the last index, otherwise false.

Constraints / 限制： - 1 <= nums.length <= 10^4 - 0 <= nums[i] <= 10^5

Example / 範例：

Input:  nums = [2,3,1,1,4]
Output: true
解釋 / Explanation: 從 index 0 跳 1 步到 index 1，再跳 3 步到最後一格。

Input:  nums = [3,2,1,0,4]
Output: false
解釋 / Explanation: 不論怎麼跳都會卡在 index 3（值為 0），無法繼續前進。

名詞解釋 / Glossary

• Greedy algorithm / 貪心演算法：每一步都做當下看起來最好的選擇，不回頭。在這題中，我們只關心「目前最遠能跳到哪裡」，不關心具體用哪條路徑到達。
• Reachable index / 可達索引：從起點出發，經過合法跳躍後可以踏上的位置。本題核心問題是：最後一個索引是否可達。
• Loop invariant / 迴圈不變式：在迴圈每一輪結束時都成立的性質。本題的不變式是「maxReach 永遠是目前能到達的最遠下標」。
• Index vs value / 索引與值：nums[i] 是位置 i 的「跳躍力」，而 i + nums[i] 才是從 i 出發能到達的最遠位置。初學者常把這兩個搞混。
• size_t / 陣列長度型別：C 語言中表示大小的無號整數型別。本題用 int 即可，因為 n <= 10^4。
• std::vector<int> / 動態陣列：C++ 標準函式庫的可變長度陣列，類似 Python 的 list。v.size() 回傳元素個數。

思路

最直覺的做法是暴力遞迴：從 index 0 出發，嘗試所有可能的跳躍長度（1 到 nums[0]），對每個落點再遞迴下去，直到踏到終點或卡住。但這樣每個位置都會被重複拜訪，最壞情況時間複雜度是指數級的，會超時。加上記憶化（memoization）可以降到 O(n²)，但對於 n = 10^4 仍然偏慢，而且空間也浪費。觀察題目的本質：我們其實不需要知道「具體怎麼跳」，只需要知道「終點是否可達」。於是引入一個貪心思路 —— 從左到右掃描，維護一個變數 maxReach，代表「目前為止能跳到的最遠下標」。對於每個位置 i，先檢查 i > maxReach（代表這格根本走不到，後面更不用看，直接回傳 false），否則用 i + nums[i] 更新 maxReach。只要某一刻 maxReach >= n - 1，就保證能到終點。這個演算法只掃一次陣列，時間 O(n)、空間 O(1)，是最優解。

The brute-force approach is recursion: from index 0, try every possible jump length (1 through nums[0]), recurse on each landing spot, and continue until we hit the end or get stuck. This explores the same positions repeatedly and degrades to exponential time. Memoization brings it down to O(n²), but for n = 10^4 that is still slow and wasteful. The key insight is that we don't need to know how to jump — only whether the end is reachable. That suggests a greedy sweep: walk left-to-right while maintaining maxReach, the farthest index we can currently reach. For each index i, first check whether i > maxReach (if so, this cell is unreachable, so the end is too — return false); otherwise update maxReach = max(maxReach, i + nums[i]). The moment maxReach >= n - 1 we are guaranteed to reach the last index. This single pass runs in O(n) time with O(1) extra space, which is optimal.

逐步走查 / Walkthrough

Trace nums = [2,3,1,1,4], n = 5, target index = 4. Start with maxReach = 0.

只用了 2 次迴圈就確定答案。注意我們沒有真的「跳」 —— 只是不斷更新「最遠可達點」。 We finished in just 2 iterations. Note that we never actually "jump" — we only keep updating the farthest reachable index.

對比 / Contrast with nums = [3,2,1,0,4]:

i=4 不可達，回傳 false。/ Index 4 is unreachable, so we return false.

Solution — C

// 演算法：貪心一次掃描。維護 maxReach = 目前能到的最遠 index；
// 若某一格 i > maxReach 表示走不到，回傳 false；若 maxReach 涵蓋終點，回傳 true。
// Algorithm: a single greedy sweep. Track maxReach = farthest reachable index so far.
// If we ever hit i > maxReach the end is unreachable; if maxReach covers n-1 we win.

#include <stdbool.h>  // 引入 bool 型別 / brings in the bool type for C

bool canJump(int* nums, int numsSize) {
    // numsSize 是 nums 陣列的元素個數；LeetCode 的 C 介面會把長度單獨傳進來
    // numsSize is the array length; LeetCode's C signature passes it separately
    int maxReach = 0;  // 目前能到的最遠 index，初始就是起點 0 / farthest reachable index, starts at 0

    for (int i = 0; i < numsSize; i++) {  // 由左到右遍歷每一格 / sweep left-to-right
        if (i > maxReach) {  // 這格根本走不到 → 後面也走不到 / cell i is unreachable, so is the end
            return false;    // 提早結束，回傳失敗 / short-circuit: return false
        }

        int jumpEnd = i + nums[i];  // 從 i 出發最遠能踏到的 index / farthest landing spot from i
        if (jumpEnd > maxReach) {   // 比現有紀錄更遠才更新 / only update if it's an improvement
            maxReach = jumpEnd;     // 更新最遠可達 / record the new best
        }

        if (maxReach >= numsSize - 1) {  // 已經能蓋到終點 / we already cover the last index
            return true;                 // 提早回傳成功 / early exit with success
        }
    }

    // 走完整個迴圈仍沒提早返回，理論上不會發生（n>=1 時 i=n-1 就會觸發上面的 true）
    // If the loop ends without returning, all cells were reachable — return true defensively.
    return true;
}

Solution — C++

// 演算法與 C 版本相同：貪心單次掃描，維護 maxReach。
// Same algorithm as the C version: one greedy pass tracking maxReach.
// 使用 std::vector 與 std::max 讓程式碼更地道 / uses std::vector and std::max for idiomatic C++.

#include <vector>     // std::vector 動態陣列 / dynamic array container
#include <algorithm>  // std::max 取最大值 / for std::max

class Solution {
public:
    // vector<int>& 是「對 vector 的參考」，避免複製整個陣列（高效）
    // vector<int>& is a reference to the vector — avoids copying the whole array
    bool canJump(std::vector<int>& nums) {
        int n = static_cast<int>(nums.size());  // 取得長度並轉成 int / get length as int
        int maxReach = 0;                       // 目前最遠可達 index / farthest reachable index

        for (int i = 0; i < n; ++i) {  // range-for 也可以，但用 index 更貼合演算法 / classic indexed loop
            if (i > maxReach) {        // i 超出可達範圍 → 終點也到不了 / i unreachable ⇒ end unreachable
                return false;          // 直接回傳失敗 / bail out
            }

            // std::max 取兩數較大者；i + nums[i] 是從 i 跳出去能踏到的最遠處
            // std::max returns the larger of two values; i + nums[i] is the farthest landing from i
            maxReach = std::max(maxReach, i + nums[i]);

            if (maxReach >= n - 1) {  // 已涵蓋最後一格 / last index is now reachable
                return true;          // 提早回傳成功 / early exit
            }
        }

        return true;  // 迴圈正常走完代表全部可達 / fallthrough: every cell was reachable
    }
};

複雜度 / Complexity

• Time: O(n) — 我們只對陣列做一次線性掃描，每一格做的是常數時間的比較與更新；n 是 nums.length。/ A single linear pass; each iteration does O(1) work. n is the length of nums.
• Space: O(1) — 只用了 maxReach、i 等少數變數，跟輸入大小無關。/ Only a handful of scalar variables; no extra structures that scale with input.

Pitfalls & Edge Cases

• 單元素陣列 / Single-element array：當 n == 1 時，起點就是終點，應該回傳 true。我們的程式在 i = 0 時 maxReach >= n - 1（0 >= 0）立即回傳 true，正確處理。/ With one element, start equals end. The check maxReach >= n - 1 fires immediately at i = 0 and returns true.
• 第一格就是 0 / Leading zero (n > 1)：例如 [0, 2, 3]，maxReach 永遠停在 0，下一輪 i = 1 > 0 立即回傳 false。陷阱在於：若忘了 i > maxReach 這個檢查，會誤以為還能往前跳。/ For [0, 2, 3], maxReach stays at 0 and the unreachable check correctly trips on i = 1. Forgetting that check would let the loop march past the wall.
• 整數溢位 / Integer overflow：i + nums[i] 最大約 10^4 + 10^5，遠小於 int 上限（~2.1×10⁹），故安全。但若題目放大限制，要小心。/ i + nums[i] peaks around 10^5 — well within int. Worth noting if constraints ever grew.
• 不需要剛好落在終點 / Don't need to land exactly on the end：跳得「超過」終點也算成功，這就是為什麼條件是 maxReach >= n - 1 而不是 == n - 1。初學者常誤寫成等號。/ Overshooting the last index still counts as reaching it — the condition is >=, not ==. A common beginner mistake.
• 混淆 index 與 value / Confusing index with value：nums[i] 是跳躍力（一個距離），不是目標 index。要到達的位置是 i + nums[i]。/ nums[i] is a jump length, not a destination. The landing index is i + nums[i].