題目描述
題目要求
給定一個非負整數陣列 nums，其中 nums[i] 代表你在索引 i 處最多可以向右跳幾步。
請判斷是否能夠從索引 0 跳到最後一個索引。
限制條件
1 <= nums.length <= 10⁴0 <= nums[i] <= 10⁵
範例
範例 1：
輸入: nums = [2,3,1,1,4]解釋：
輸出: True
從索引 0，我們可以：
- 跳 1 步 到索引
1，再跳 3 步 到最後一個索引。 - 或者直接跳 2 步 到索引
2，再跳 2 步 到最後一個索引。
不管怎樣，我們都能抵達最後。
範例 2：
輸入: nums = [3,2,1,0,4]
輸出: False
解釋：
從索引 0，我們可以：
- 跳到索引
1，再跳到索引2，再跳到索引3。 - 但索引
3的nums[3] = 0，卡住了，無法繼續前進。
解題思路
這題的核心是如何有效率地判斷是否能走到最後。
思路 1：貪心演算法（Greedy）
- 記錄當前可以到達的最遠距離
max_reach。 - 每次迴圈遍歷
nums[i]時，不斷更新max_reach。 - 如果
max_reach超過或等於最後一個索引，則回傳True。 - 如果
max_reach無法再前進（也就是max_reach == i且nums[i] == 0），則回傳False。
思路 2：動態規劃（DP）
- 建立一個
dp陣列，dp[i]表示索引i是否能到達。 - 遍歷
nums，如果dp[i]為True，則將dp[i+1]~dp[i+nums[i]]設為True。 - 最後檢查
dp[n-1]是否為True。
解法一：貪心演算法（Greedy）
思路
- 建立變數
max_reach = 0來追蹤目前可達的最遠範圍。 - 遍歷
nums陣列，每次更新max_reach = max(max_reach, i + nums[i])。 - 若
max_reach >= 最後一個索引，則回傳True（表示能夠抵達）。 - 若在遍歷過程中，
i > max_reach，則回傳False（表示卡住了）。
程式碼
class Solution:
def canJump(self, nums: List[int]) -> bool:
max_reach = 0
for i in range(len(nums)):
if i > max_reach: # 代表已經無法前進
return False
max_reach = max(max_reach, i + nums[i])
if max_reach >= len(nums) - 1: # 代表已經能到終點
return True
return True
時間與空間複雜度
- 時間複雜度：O(n)（只遍歷一次
nums） - 空間複雜度：O(1)（只使用常數額外變數）
解法二：動態規劃（DP）
思路
- 建立
dp陣列，dp[i] = True表示索引i可達。 - 初始化
dp[0] = True，因為起點一定能到達。 - 遍歷陣列，若
dp[i] == True，則標記dp[i+1] ~ dp[i+nums[i]]為True。 - 最後檢查
dp[n-1]是否為True。
程式碼
class Solution:
def canJump(self, nums: List[int]) -> bool:
n = len(nums)
dp = [False] * n
dp[0] = True # 起點一定可達
for i in range(n):
if dp[i]: # 只有當前可達時，才標記後面
for j in range(1, nums[i] + 1):
if i + j < n:
dp[i + j] = True
return dp[n - 1] # 檢查最後一個索引是否可達
時間與空間複雜度
- 時間複雜度：O(n²)（最差情況下，每個索引都影響
nums[i]個索引） - 空間複雜度：O(n)（需要額外的
dp陣列）
結論
貪心演算法（Greedy） 是最適合的解法，因為它只需要 O(n) 時間，且不需要額外空間。
這題的本質就是：你每次跳躍時，都應該確保「最遠能夠抵達的地方」，而不是關心具體的跳躍方式。如果 max_reach 能夠超過最後一個索引，那就一定能成功！
