問題背景

本文背景是leetcode的一道經典題目：跳躍游戲，描述如下：

給定一個非負整數數組 nums，初始位于數組的第一個位置（下標0）。數組中的每個元素表示在該位置可以跳躍的最大長度。判斷是否能夠到達最后一個下標。

?示例?：

• 輸入：[2,3,1,1,4] → 輸出：true
• 輸入：[3,2,1,0,4] → 輸出：false

解題思路

貪心算法解法

?核心思想?：維護一個當前能夠到達的最遠位置，遍歷數組時不斷更新這個值。

算法步驟分解

1. 初始化 max_reach = 0（當前能到達的最遠位置）
2. 遍歷數組：
   • 如果當前位置 i > max_reach，說明無法到達，返回 false
   • 更新 max_reach = max(max_reach, i + nums[i])
   • 如果 max_reach ≥ 最后一個下標，提前返回 true
3. 遍歷結束返回 true

代碼實現

class Solution {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]);if (maxReach >= nums.length - 1) return true;}return true;}
}

算法原理解析

1. ?初始化?：maxReach 記錄當前能到達的最遠位置
2. ?遍歷過程?：
   • 檢查當前位置是否可達（i > maxReach）
   • 更新最遠可達位置（i + nums[i]）
   • 提前終止條件（已到達終點）
3. ?返回值?：遍歷完成仍未返回，說明可以到達終點

示例分析

?示例1?：[2,3,1,1,4]

i=0: maxReach = max(0, 0+2)=2
i=1: 1<=2 → maxReach = max(2, 1+3)=4 (覆蓋終點)
直接返回true

?示例2?：[3,2,1,0,4]

i=3: maxReach=3
i=4: 4>3 → 返回false

常見誤區

1. ?錯誤解法?：簡單檢查是否有0存在
   • 反例：[2,0,2,0,1]可以到達終點。
2. ?過度優化?：不需要記錄具體路徑

實際應用

1. 網絡路由選擇
2. 游戲關卡設計
3. 資源調度問題