跳跃游戏

LeetCode-55

// 这道题目属于贪心算法（Greedy Algorithm）的范畴，需要遍历整个数组，记录能够到达的最远位置，并判断是否能到达当前下标的位置。

// 时间复杂度：O(n)
// 空间复杂度：O(1)

// i说明你一步一步走，nums[i](当前值)说明你可以跳的最大距离)，如果你跳的最大距离还没有你一步一步走的快，那说明你跳不出去

var canJump = function (nums) {
  let len = nums.length
  let maxIndex = 0 // 能够到达的最远位置
  for (let i = 0; i < len; i++) {
    // 若当前下标超出了能够到达的最远位置，返回false
    if (i > maxIndex) return false

    // 更新能够到达的最远位置 i为当前所处步骤, nums[i]为最远可以跳多少步骤
    maxIndex = Math.max(maxIndex, i + nums[i])
    // 若能够到达最后一个位置，则返回true【每个元素代表可以跳小于或等于(元素步)】
    // 【超出没关系，核心是证明能到达最后一步】
    if (maxIndex >= len - 1) {
      return true
    }
  }
  return false
}