贪心算法之跳跃游戏

📅 发布时间:2026/7/6 14:33:26 👁️ 浏览次数:
贪心算法之跳跃游戏
一、贪心思路拆解核心逻辑:局部最优:遍历数组时,不断更新“当前能跳到的最远距离”(覆盖范围);全局最优:如果这个覆盖范围能包含数组最后一个下标,就返回true;如果遍历完覆盖范围还没到终点,返回false。关键观察:数组中每个元素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