55. 跳跃游戏

[Geekhyt]

原题链接

先明确，题目给出的非负整数数组中的每个位置的数字都对应着其最大的跳跃能力，要求我们判断能否到达最后一个下标。

到达或是超过都是可以满足要求的，因为每个位置的数字代表的是其最大的跳跃能力，而不是固定的跳跃能力(大富翁游戏)。

所以只需要判断能否到达终点即可：

1. 定义能够跳的最远位置 canJumpMax，初始化为 0。
2. 遍历数组，如果当前值大于 canJumpMax 则不能跳到末尾返回 false。
3. 每个位置都可以作为起跳点，将 canJumpMax 不断更新，i + nums[i] 也就是当前位置能够跳到的最远位置。
4. 如果可以跳到最后即成功返回 true。

const camJump = function(nums) {
    let canJumpMax = 0
    let len = nums.length
    for (let i = 0; i < len; i++) {
        if (i > canJumpMax) {
            return false
        }
        canJumpMax = Math.max(canJumpMax, i + nums[i])
    }
    return true
}

• 时间复杂度: O(n)
• 空间复杂度: O(1)