ARTICLE DETAIL

资讯详情

深耕网站建设、视觉设计与SEO优化的一线实战洞察。

贪心算法之跳跃游戏

贪心算法之跳跃游戏

一、贪心思路拆解

  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
返回列表