55. Jump Game

📘 題目敘述

給你一個整數陣列 nums。你一開始站在陣列的第一個索引位置。

陣列中的每個元素 nums[i] 代表你從索引 i 最多可以往前跳的步數。

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

條件限制

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 10^5

🧠 解題思路

我這份寫法是從右往左掃，反過來想：

我不直接問「從起點能不能跳到終點」，而是問：

我現在距離「某個可以到達終點的位置」還差幾步？

所以我用 count 表示：如果我站在目前位置 i，要到達「右邊那個已知能到終點的位置」至少還需要跳幾步。

掃描時有兩種情況：

• 如果 nums[i] >= count，代表從 i 這格一跳就能跨過去（或剛好到達）那個目標位置 那 i 本身也就變成「新的可以到終點的位置」，我把 count 重新設成 0。
• 不管能不能更新目標位置，往左移一格時，「距離目標」都會多 1，所以每輪最後 count++。

最後如果最左邊（i = 0）也能成為「可到終點的位置」，那整體就成功。

所有變數

• count：目前位置到右邊「可到終點的目標位置」所需要的最少步數（距離）

🪜 主要流程步驟

1. 從最右邊開始掃，先把 count 設成 -1

我用 count = -1 的原因是：第一輪在最右邊 i = n-1 時，會先檢查再 count++，這樣可以讓「終點本身」被視為距離 0 的目標。

2. 由右到左逐格檢查：這格能不能成為新的目標點

對每個索引 i（從 n-1 到 0）：

如果 nums[i] >= count 代表從 i 出發，跳躍能力足以到達目前的目標位置（或超過），所以我把 count = 0，表示「目標點更新成 i」。

3. 每往左移一格，距離目標就 +1

不管剛剛有沒有更新目標點，下一輪 i 會往左一格，所以距離一定多 1，我做 count++。

4. 看最後起點能不能成為目標點

如果起點可以到終點，那掃完後會呈現 count == 1，我就回傳 true；否則回傳 false。

⏱️ 複雜度

• 時間複雜度：O(n)，只掃一次陣列
• 空間複雜度：O(1)

💻 程式碼實作

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int count = -1;
        for (int i = nums.size() - 1; i >= 0; i--) {
            if (nums[i] >= count) {
                count = 0;
            }
            count++;
        }
        return (count == 1);
    }
};

🔗 題目連結

https://leetcode.com/problems/jump-game/