45. Jump Game II

題目 / Problem

中文： 給定一個 0-indexed 整數陣列 nums，長度為 n。你一開始站在 index 0。

陣列中每個元素 nums[i] 代表從 index i 出發最多能向前跳的步數。也就是說，當你在 index i 時，可以跳到任何 index (i + j)，只要：

• 0 <= j <= nums[i]，並且
• i + j < n

請回傳到達 index n - 1 所需的最少跳躍次數。題目保證一定能到達終點。

English: You are given a 0-indexed integer array nums of length n. You start at index 0. Each nums[i] is the maximum jump length from index i. Return the minimum number of jumps needed to reach index n - 1. It is guaranteed that the last index is reachable.

Constraints: - 1 <= nums.length <= 10^4 - 0 <= nums[i] <= 1000 - The last index is always reachable.

Example:

Input:  nums = [2,3,1,1,4]
Output: 2
Explanation: 0 → 1 (跳 1 步), 1 → 4 (跳 3 步). 共 2 次跳躍.

名詞解釋 / Glossary

• Greedy algorithm / 貪婪演算法：每一步都做「當下看起來最好」的決定，並且能證明這樣做會得到最終最優解。本題每次都選擇「能跳到最遠位置」的下一步。
• BFS-style layering / BFS 分層思維：把每次跳躍想成 BFS 中的一層。第 k 次跳躍能到達的所有 index 構成一個「區間」，下一次跳躍能到達的最遠位置就是這個區間內所有 i + nums[i] 的最大值。
• Range / 區間：本題用兩個變數 currentEnd 與 farthest 表示「目前這一跳的右邊界」和「下一跳能達到的最遠處」。
• 0-indexed / 從 0 開始計數：陣列第一個元素的 index 是 0，最後一個是 n - 1。
• In-place / 原地處理：本演算法只用幾個整數變數，不需要額外陣列，是空間 O(1) 的。

思路

最直覺的做法是動態規劃 (DP)：令 dp[i] 為從 0 跳到 i 的最少次數，對每個 i 試所有可能的前一個位置 j，取 dp[j] + 1 的最小值。但這樣是 O(n²)，當 n = 10^4 時是 10^8 次操作，雖然能過但相對較慢，而且這題其實有更聰明的解法。觀察跳躍的本質：當你已經跳了 k 次，能到達的位置是一個連續區間 [0, R_k]，因為你可以選擇短跳或長跳到區間內任何位置。從這個區間出發，第 k+1 次跳躍能到達的最遠處是 max(i + nums[i])，其中 i 屬於這個區間。所以我們只要從左到右掃一遍，維護兩個變數：currentEnd（目前這一跳能到的最右邊）和 farthest（如果現在再跳一次，最遠能到哪）。每當 i 走到 currentEnd，就代表這一層走完了，必須再跳一次，於是把 currentEnd 更新為 farthest 並把 jumps 加 1。注意只掃到 n - 2 即可，因為若 i = n - 1 已經是終點，不需要再起跳；若多掃一格會多算一次跳躍。

The brute-force approach is dynamic programming where dp[i] is the minimum jumps to reach index i, but that's O(n²). The key insight for an O(n) greedy solution is that after k jumps, the set of reachable indices forms a contiguous range [0, R_k] — you can always choose to jump less, so anything within that range is reachable. From this range, the farthest reachable index in k + 1 jumps is max(i + nums[i]) over all i in the range. So we sweep left to right while tracking two values: currentEnd (the right boundary of indices reachable in the current jump count) and farthest (the right boundary if we make one more jump). Whenever the loop index i hits currentEnd, we must commit one more jump, so we increment jumps and set currentEnd = farthest. We only iterate up to n - 2 — once we land at or beyond n - 1, we're done; iterating to n - 1 would over-count by one.

逐步走查 / Walkthrough

Example: nums = [2,3,1,1,4], n = 5. We loop i from 0 to n - 2 = 3.

Loop ends (we stop at i = 3, since i = 4 is the destination). Final answer: jumps = 2 ✓

中文解讀： - i = 0：第 1 跳的邊界是 0（起點本身），所以 i == currentEnd，我們把 jumps 加成 1，currentEnd 更新為 2（從 0 最遠能到 index 2）。 - i = 1：still inside [0, 2]，更新 farthest = 4（從 1 能跳到 index 4）。 - i = 2：碰到 currentEnd = 2 邊界，必須再跳一次。jumps = 2，currentEnd = 4，已涵蓋終點。 - i = 3：still inside [0, 4]，沒碰到邊界，不再加跳。

Solution — C

// 演算法 / Algorithm:
// 貪婪 + BFS 分層思維。維護「目前這跳的右邊界 currentEnd」與「下一跳最遠能到 farthest」。
// Greedy with BFS-layer thinking. Track current-jump right boundary and the farthest
// reachable if we made one more jump. When i hits currentEnd, commit a jump.
// Time O(n), Space O(1).

#include <stdio.h>   // 標準 I/O，用於本機測試 / standard I/O for local testing

// 簡單的 max 巨集 / simple max macro
#define MAX(a, b) ((a) > (b) ? (a) : (b))
//                ^ 三元運算子: 如果 a>b 取 a，否則取 b
//                ^ ternary: pick a if a>b, else b

int jump(int* nums, int numsSize) {
    // numsSize 是陣列長度 n / numsSize is the array length n
    // nums 是一個 int* (指向陣列首元素的指標) / nums is an int* (pointer to first element)

    int jumps = 0;        // 已跳次數 / number of jumps taken so far
    int currentEnd = 0;   // 目前這一跳能到達的最右 index / right boundary of current jump layer
    int farthest = 0;     // 下一跳最遠能到達的 index / farthest reachable in one more jump

    // 只掃到 n-2 (含)。若 i 走到 n-1，就代表已經在終點，不需再起跳。
    // Loop only to n-2. If i reached n-1, we're already at the goal; no more jumps needed.
    for (int i = 0; i < numsSize - 1; i++) {
        // 從 index i 最遠能跳到 i + nums[i] / from i we can reach i + nums[i]
        // nums[i] 等同於 *(nums + i)，是指標索引語法 / nums[i] is *(nums + i), pointer indexing
        int reach = i + nums[i];

        // 更新「下一跳能到的最遠處」 / update the farthest reachable in one more jump
        farthest = MAX(farthest, reach);

        // 走到目前這一跳的右邊界，必須再跳一次。
        // We've consumed this jump's range; commit one more jump.
        if (i == currentEnd) {
            jumps++;                  // 跳一次 / make a jump
            currentEnd = farthest;    // 進入下一層的右邊界 / move to next layer's boundary

            // 小優化：若已能涵蓋終點，可提前結束。
            // Optimization: if we can already reach the end, break early.
            if (currentEnd >= numsSize - 1) break;
        }
    }

    return jumps;  // 回傳最少跳躍次數 / return the minimum number of jumps
}

Solution — C++

// 演算法 / Algorithm:
// 與 C 版相同的貪婪解法，O(n) 時間 O(1) 空間。
// Same greedy O(n)-time, O(1)-space algorithm as the C version.

#include <vector>      // 提供 std::vector / provides std::vector
#include <algorithm>   // 提供 std::max / provides std::max

class Solution {
public:
    // vector<int>& 是「對 vector<int> 的引用」，避免複製整個陣列。
    // vector<int>& is a reference to a vector — passes by reference, no copy.
    int jump(std::vector<int>& nums) {
        int n = static_cast<int>(nums.size());  // 取陣列長度，轉成 int / get size as int
        int jumps = 0;        // 已跳次數 / jump count
        int currentEnd = 0;   // 目前這跳的右邊界 / current jump's right boundary
        int farthest = 0;     // 下一跳能到的最遠處 / farthest reachable in one more jump

        // 只掃到 n-2，避免在 i = n-1 時多算一次跳躍。
        // Iterate only up to n-2 to avoid over-counting at the last index.
        for (int i = 0; i < n - 1; ++i) {
            // std::max 取兩數中較大者 / std::max returns the greater of two values
            farthest = std::max(farthest, i + nums[i]);

            // 抵達邊界時，必須再消耗一次跳躍。
            // When i reaches currentEnd, we must spend one more jump.
            if (i == currentEnd) {
                ++jumps;                   // 前綴遞增，比 jumps++ 略快但結果相同
                                           // pre-increment, semantically same as jumps++
                currentEnd = farthest;     // 進入下一層 / move to next layer

                // 提前結束：已能涵蓋終點 / early exit: end is reachable
                if (currentEnd >= n - 1) break;
            }
        }

        return jumps;  // 回傳答案 / return the answer
    }
};

複雜度 / Complexity

• Time: O(n) — 我們對陣列只做一次線性掃描，每個 index 做 O(1) 工作（更新 farthest、比較邊界）。n 是 nums.length。 / We sweep the array once, doing O(1) work per index.
• Space: O(1) — 只用了 jumps、currentEnd、farthest 三個整數，不隨輸入大小成長。 / Only three integer variables, independent of n.

Pitfalls & Edge Cases

• 掃到 n - 1 會多算一次 / Iterating up to n - 1 over-counts：若迴圈條件寫成 i < n 而非 i < n - 1，當 i = n - 1 時可能再次觸發 i == currentEnd 而把 jumps 多加一次。本解只掃到 n - 2。
• 單元素陣列 / Single-element array：nums.length == 1 時起點即終點，迴圈完全不執行，回傳 0，正確。 / When the array has one element we're already at the goal; the loop body never runs and we return 0.
• nums[i] == 0 是否會卡住 / Can a zero stall us?：題目保證一定能到達終點，所以即使路上有 0 也不會出現「無法前進」的情形。我們的演算法不需特別處理。 / The problem guarantees reachability, so zeros won't strand us.
• 不要記錄具體跳到哪個 index / Don't track the exact landing index：貪婪法只需要知道「最遠能到」，不必真的決定每次跳到哪個位置 — 這是本題能 O(n) 的關鍵。 / The greedy proof relies on tracking the farthest reach, not the actual landing positions.
• 整數溢位 / Integer overflow：i + nums[i] 最多約 10^4 + 1000，遠小於 int 上限，無溢位風險。 / i + nums[i] stays well within int range given the constraints.
• 不要用 i <= currentEnd 之類的條件 / Avoid off-by-one boundary checks：邊界判斷用 i == currentEnd（嚴格相等）即可；任何提前或延後都會讓 jumps 計數錯誤。 / Use strict equality i == currentEnd — shifting it by one breaks the count.