今天接力昨天的貪婪演算法：

題目

55. Jump Game
    給定一個非負整數陣列 nums，其中 nums[i] 代表在第 i 個位置最多能跳的步數。請判斷能否從起點跳到最後一個位置。

程式碼

Java 解法

public boolean canJump(int[] nums) {
int maxReach = 0;
for (int i = 0; i < nums.length; i++) {
if (i > maxReach) return false;
maxReach = Math.max(maxReach, i + nums[i]);
}
return true;
}

Python 解法

def canJump(nums):
max_reach = 0
for i in range(len(nums)):
if i > max_reach:
return False
max_reach = max(max_reach, i + nums[i])
return True

range(len(nums))：會生成一個從 0 開始、到 len(nums)-1 結束的數列。
for i in range(len(nums)):：表示 i 會依序取這個數列的值，從頭到尾掃過整個陣列的意思。
max_reach 的意思是：目前能夠跳到的最遠位置，max_reach = max(max_reach, i + nums[i]) 。
這題的程式邏輯幾乎一樣：Java 需要嚴謹的變數型別宣告，像 int maxReach = 0; ，並用 Math.max() 更新最大值；Python 比較簡單，直接寫 max_reach = 0，用內建函式 max() 就能完成。

測試案例解析

Case 1

print(canJump([2,3,1,1,4]))

• 起點 nums[0] = 2，可以跳到 index=1 或 index=2
• 從 index=1 (值=3) 可以再往前跳到最後一個位置
  可以到達最後 → True

Case 2

print(canJump([3,2,1,0,4]))

• 起點 nums[0] = 3，可以到達 index=1、2、3
• 但 index=3 的值 = 0，表示卡住無法再跳
• 因此無法到達最後一個位置
  結果 → False

複雜度分析

• 時間複雜度：O(n) → 只需遍歷一次陣列，每一步更新最遠可達範圍。
• 空間複雜度：O(1) → 只使用一個變數 maxReach。

心得

這題核心思路是 「動態更新最遠可達位置」：
用貪婪法記錄目前能跳到的最遠範圍。如果走到某個位置發現「超過能到的範圍」，那就直接判定失敗；如果一路都能走到，最後一定可以抵達終點。
貪婪法的優勢在於：不用回頭看也不用窮舉，只要作出「能跳最遠」的選擇，就能正確判斷結果。這讓演算法保持在 O(n) 的效率。