贪心算法判断数组终点可达性：维护最大位置（LeetCode 55）

---

题目描述

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

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

示例 1:

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

示例 2:

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

提示:

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

贪心算法

核心思路

维护一个变量 max，表示当前能够到达的最远位置。遍历数组时，对于每个位置 i，如果 i 在当前能够到达的范围内（即 i <= max），则更新 max 为 max 和 i + nums[i] 中的较大值。如果 max 已经大于或等于数组的最后一个位置（即数组长度减一），则说明可以到达最后一个位置，返回 true。如果遍历结束都没有达到最后一个位置，则返回 false。

这种方法确保了在每一步都贪心地扩展最远可达距离，从而高效地判断是否可达。

代码实现

public boolean canJump(int[] nums) {
    int len = nums.length; // 数组长度
    int max = 0; // 当前能到达的最远位置
    for (int i = 0; i < len; i++) {
        // 如果当前索引i在可达范围内，才更新最远位置
        if (i <= max) {
            // 更新最远可达位置：取当前最远位置和i + nums[i]的较大值
            max = Math.max(max, i + nums[i]);
            // 如果最远可达位置已经超过或等于最后一个位置，则返回true
            if (max >= len - 1) {
                return true;
            }
        }
    }
    return false; // 遍历结束仍未到达最后位置，返回false
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度。我们只需要遍历数组一次。
• 空间复杂度：O(1)，只使用了常数级别的额外空间。

来源

55. 跳跃游戏 | 力扣（LeetCode）

---