【面试经典150题】跳跃游戏

题目链接

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

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

• 1 <= nums.length <= $10^4$
• 0 <= nums[i] <= $10^5$

分析：

假设当前位于nums[i]，表示该元素后面的nums[i]个元素任我跳，那该跳哪个呢？

是不是得考虑跳到哪一个位置下下一步可以跳得更远。这个由index+nums[i]决定。

也就是说后面的nums[i]个元素里，哪个索引+元素值最大就跳到哪里。

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function (nums) {
    let i = 0;
    let nextIndex;
    let maxVal = 0;
    while (i + nums[i] < nums.length - 1) {
        if (nums[i] === 0) {
            return false;
        }
        for (let j = i + 1; j <= i + nums[i]; j++) {
            if (j + nums[j] > maxVal) {
                nextIndex = j;
                maxVal = j + nums[j];
            }
        }
        maxVal = 0;
        i = nextIndex;
    }
    return true;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

时间复杂度：$O(n^2)$

空间复杂度：$O(1)$

时间复杂度太高，换个思路：

维护一个最大可达位置maxReach。

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function (nums) {
    let maxReach=0;
    for(let i=0;i<nums.length;i++){
        if(i>maxReach){
            return false;
        }
        maxReach=Math.max(maxReach,i+nums[i]);
        if(maxReach>=nums.length-1){
            return true;
        }
    }
    return true;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

时间复杂度：$O(n)$

空间复杂度：$O(1)$