贪心算法之跳跃游戏

一、贪心思路拆解

1. 核心逻辑：

   • 局部最优：遍历数组时，不断更新“当前能跳到的最远距离”（覆盖范围）；
   • 全局最优：如果这个覆盖范围能包含数组最后一个下标，就返回true；如果遍历完覆盖范围还没到终点，返回false。

2. 关键观察：

   • 数组中每个元素nums[i]表示“从i位置能跳的最大长度”，所以从i位置能到达的最远距离是i + nums[i]；
   • 遍历过程中，只要当前下标i在“已有的覆盖范围”内，就可以用i + nums[i]更新覆盖范围；
   • 一旦覆盖范围 >= 数组最后一个下标，直接返回true（不用再遍历，提前终止更高效）。

二、分步理解（结合示例）

示例1：nums = [2,3,1,1,4]

• 初始：覆盖范围cover = 0（起始位置0，能跳2步，初始覆盖到0）；
• 遍历i=0（在cover内）：更新cover = max(0, 0+2) = 2（现在能覆盖到0、1、2）；
• 遍历i=1（在cover内）：更新cover = max(2, 1+3) = 4（覆盖到0-4，已包含最后一个下标4），返回true。

示例2：nums = [3,2,1,0,4]

• 初始：cover = 0；
• 遍历i=0：cover = max(0, 0+3) = 3（覆盖0-3）；
• 遍历i=1：cover = max(3, 1