算法练习21：跳格子(leetcode 55)

题目

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

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

解题

遍历这个数组里的格子数，更新其能跳到的最远距离，当能跳到的最远距离大于等于最后一个下标时，代表着可以跳到。
[2,3,1,1,4]

• 第1步，下标0，数字2，能跳到的最远距离 arrDes = 0+2 = 2
• 第2步，下标1 < arrDes，说明这个格子是能跳到的，所以计算这个格子能跳的最远距离 arrDes1 = 1 + 3 = 4，明显，这个距离比上个arrDes大，即arrDes1 > arrDes，所以更新arrDes = Math.max(arrDes, arrDes1) = 4，发现arrDes = 数组最后一个下标4，说明它能跳到最后，返回true，结束
• 如果发现当前遍历的下标，大于能跳到的最远距离时，说明永远无法跳到最后了

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
    // 代表当前可跳到的最远可达点
    let arriveDes = 0;
    for(let i = 0; i < nums.length; i++) {
        // 如果当前格子数下标数，小于等于能跳到的最远距离，就继续遍历计算最远距离
        if(i <= arriveDes) {
            arriveDes = Math.max(arriveDes, i + nums[i])
            if(arriveDes >= nums.length - 1) return true;
        // 否则，当格子下标数超过可跳到的最远距离，代表着永远不可能到最远距离了
        }else{
            return false;
        }
    }
};
console.log(canJump([2,3,1,1,4])) // true