题目描述

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例：
输入：nums = [3,2,1,0,4]
输出：false

题目分析

表面看是个搜索问题，用 DFS 或 BFS 都能解决，但时间复杂度太大。
其实问题的关键点是“最大长度”，意味着可以计算出跳跃至右侧的最大边界，在边界左侧都是可以到达的，不需要回溯。
所以只需要在边界内每次向右移动1位，同时计算新的最大跳跃是否超出边界，如果超出边界，则更新边界。最后判断边界是否超出最后一个下标即可。
时间复杂度 O(n)

Java

public boolean canJump(int[] nums) {
    int cur = 0, right = nums[0];
    while (cur <= right && right < nums.length) {
        right = Math.max(cur + nums[cur], right);
        cur++;
    }
    return right >= nums.length - 1;
}

Kotlin

fun canJump(nums: IntArray): Boolean {
    var cur = 0
    var right = nums[cur]
    while (right in cur until nums.size) {
        right = max(right, cur + nums[cur])
        cur++
    }
    return right >= nums.size - 1
}