题目描述

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

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

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

样例

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

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

算法1

(暴力枚举) $O(n)$

思路: x + nums[x] > y,当x 索引的位置加上 nums[x] 能够 > y 的时候, 那么x 必然能够到达y 位置. 如果数组中有一个索引位置x + nums[x] > nums.length - 1, 那就在一个位置能够跳跃到数组的最后一位.所以我们现在就要找到这个索引x 位置.

举个栗子:
要查找数组:nums = [3,2,1,0] 中能否有一个位置能跳跃到最后一位的位置
数组第一位: 0 + nums[0] = 0 +3 = 3,能够到达数组的最后一位,并且前3 位都能够通过: i + nums[i] >= nums.length - 1,说明都能够到达数组的最后一位。
但是如果把数组变成: nums = [3,2,1,0,4], 虽然前三位都能够到达数组的倒数第二位,但是也仅仅能够到达这个位置,毕竟倒数第二位:nums[2] = 0。并且在前3 位的计算中: i + nums[i] 最大也只能够到达nums 数组的倒数第二位,所以此时我们就要有一个想法: 我们在一个范围内找到一个比当前范围还要大的范围,这样才能够跳出当前的范围去往更大的范围,而这个范围公式就是通过: i + nums[i] 来得到的,因为我们并不知道最大范围是什么,所以就先把nums[0] 作为最大范围,然后查找在这个范围中,有没有大于这个范围的数,如果没有的话,那么就只能够困在这个范围中,如果当前的最大范围: i + nums[i] < nums.length - 1,那么就永远无法跳到数组的最后一位了.

时间复杂度

最坏的情况只是遍历一次数组，所以时间复杂度:O(n)

参考文献

Java 代码

class Solution {

    public boolean canJump(int[] nums) {
        int dist = nums[0];
        for(int i = 0; i < nums.length; i++){
            if(dist < i) return false; //如果连i 都无法到达,那不可能到达y(nums.length -1 )的位置: i + nums[i] >= nums.length - 1
            dist = Math.max(i + nums[i],dist);
        }

        return dist >= nums.length - 1;
    }
}