55.跳跃游戏

Problem: 55. 跳跃游戏

思路

在遍历数组的过程中，易知可跳到的范围会随着遍历的深入越来越远，因此只需在遍历过程中维护可跳到的最远距离，看是否能遍历完整个数组即可。

解题过程

设max为从数组起点能到达的最远距离，在遍历到某一点时，若该点可及，也就是说max<i，则尝试更新在加入这一点后的所能到达的最远距离i + nums[i]。

复杂度

• 时间复杂度: $O(n)$：最多遍历一遍数组。
• 空间复杂度: $O(1)$：若干常量。

Code

class Solution {
    public boolean canJump(int[] nums) {
        int max = 0;
        max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (max < i) return false;
            max = Math.max(max, i + nums[i]);
        }
        return true;
    }
}