跳跃游戏

题目#

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 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 <= 10^4
• 0 <= nums[i] <= 10^5

解题思路

1. 定义一个变量 maxReach 用来记录当前可以到达的最远下标。初始时，我们在数组起始点，因此 maxReach = 0。

2. 从下标 0 开始，依次遍历数组中的每个位置 i。

   • 判断当前位置是否能到达：
     • 如果当前下标 i 超过了 maxReach，这说明我们之前无论怎么跳都无法到达这个位置，所以就没办法继续往前跳，直接返回 false。
   • 更新最远可达位置：
     • 如果当前位置可以到达（即 i <= maxReach），我们就更新 maxReach。如何更新呢？
       • 在位置 i，你可以跳跃的最大步数为 nums[i]，所以从 i 出发，你最远可以到达的位置是 i + nums[i]。
       • 我们将 maxReach 更新为 Math.max(maxReach, i + nums[i])，即比较当前记录的最远位置和从当前位置跳跃后能到达的最远位置，取较大值。
   • 提前判断是否到达终点：
     • 如果在任何时刻 maxReach 大于或等于最后一个下标（即 nums.length - 1），说明可以跳到最后一个位置，直接返回 true。

3. 如果整个数组都遍历完了，都没有能够返回 true，那么在循环结束后返回 false.

代码实现

/**
 * nums - 代表你在该位置可以跳跃的最大长度，例如 [2,3,1,1,4]
 */
function canJump(nums) {
  let maxReach = 0

  for (let i = 0; i < nums.length; i++) {
    if (i > maxReach) return false

    // 更新 maxReach，取“当前已知的最远距离”和“从当前位置能够跳到的最远距离”的最大值
    maxReach = Math.max(maxReach, i + nums[i])

    // 接下来就看更新的 maxReach 是否到达了最后一个下标
    if (maxReach >= nums.length - 1) return true
  }

  // 遍历结束之后，仍然没有跳到最后，返回 flase
  return false
}

-EOF-