6. 跳跃游戏（55）

一、题目内容 中等

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。

示例1：

输入：nums = [2,3,1,1,4] 输出：true 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例2：

输入：nums = [3,2,1,0,4] 输出：false 解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

提示：

• 1 <= nums.length <=
• 0 <= nums[i] <=

二、解题思路

题目提示，数据很大，说明不能用递归，必定超时。
这道题解法妙就妙在，for 循环的判断条件可以动态变化，这种写法写得不对，就容易错。

1. 递归法（超时）

每次我们所在格子的位置索引设为 start，所在格子可跳跃步数为 step。
我们是想每次都走最远的距离，只要能证明 start + step >= nums.length - 1就是可达的。
按照这种想法，我们容易写出递归。

1. 贪心

我们换个思路，我们所在格子位置设为 start，目前跳跃时可覆盖的最远位置设为 cover。
我们每次跳跃，都比较新的 cover 和 旧的 cover 谁更远，选择更远的来走。
局部最大，能得到全局最大。如果还是不可达，说明真的走不到。

三、具体代码

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function (nums) {
  const end = nums.length - 1;
  if (!end) return true;
  let cover = 0;
  for (let start = 0; start <= cover; start++) {
    const newCover = start + nums[start];
    cover = Math.max(newCover, cover)
    if(cover >= end) return true
  }
  return false
};
/**
 * 时间复杂度：O(n)
 * 空间复杂度：O(1)
 */

四、其他解法