55 跳跃游戏

一、题目

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

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

二、题解

思路：

这道题的核心不在于去模拟每一步具体跳到了哪里，而是去维护一个“当前能到达的最远距离”（设为 maxReach）。

1. 遍历数组中的每一个位置 $i$。
2. 检查可达性： 如果当前遍历到的位置 $i$ 已经大于了我们之前计算出的 maxReach，说明我们连位置 $i$ 都到不了，更别提走到最后了，直接返回 false。
3. 更新最远距离： 如果当前位置 $i$ 是可达的，那么从这个位置出发，我们最远能到达的距离就是 $i + nums[i]$。我们将 maxReach 更新为 maxReach 和 $i + nums[i]$ 中的较大值。
4. 提前终止： 在遍历过程中，如果发现 maxReach 已经大于或等于数组的最后一个下标，说明已经可以到达终点，直接返回 true。

class Solution {
    public boolean canJump(int[] nums) {
        // 记录当前能到达的最远下标
        int maxReach = 0;

        for (int i = 0; i < nums.length; i++) {
            // 如果当前位置超出了能到达的最远范围，说明无法继续向后走了
            if (i > maxReach) {
                return false;
            }

            // 更新能到达的最远下标
            maxReach = Math.max(maxReach, i + nums[i]);

            // 如果最远能到达的下标已经包含了最后一个位置，直接返回 true
            if (maxReach >= nums.length - 1) {
                return true;
            }
        }

        return true;
    }
}

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

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