LeetCode Jump Game：能否到達終點 — 貪心單次遍歷

題目描述

數組每個元素表示在該位置最多能向前跳躍的步數。判斷是否存在一種跳法能到達最後一個下標。

範例：

輸入: [2,3,1,1,4] → true
輸入: [3,2,1,0,4] → false

解題思路：維護最遠可達位置

• 遍歷數組，維護 farthest = 當前能到達的最遠下標。
• 若遍歷到 i > farthest，說明卡住了，返回 false。
• 若 farthest >= n-1，提前返回 true。
• 每步更新 farthest = max(farthest, i + nums[i])。

參考代碼 (Python)

class Solution:
    def canJump(self, nums):
        farthest = 0
        n = len(nums)
        for i in range(n):
            if i > farthest:
                return False
            farthest = max(farthest, i + nums[i])
            if farthest >= n - 1:
                return True
        return False

複雜度分析

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