LeetCode 55. 跳跃游戏

◎

本节目标

维护已扫描位置能够到达的最远下标，判断终点是否可达。

这是单序列扫描与边界的可达性模型。路径不必逐条枚举，因为所有已访问位置的能力可以压缩成一个最远边界。

题意与约束

位于下标 i 时最多向右跳 nums[i] 步，初始在 0，判断能否到达最后一个下标。

直接思路与瓶颈

从每个位置分叉搜索所有落点会产生指数级路径。不同路径若都能到达同一或更靠右的位置，本质上没有必要分别保留。

贪心模型与算法推导

维护 farthest，它表示已扫描且可达的位置能到达的最远下标。扫描位置 i 时若 i>farthest，说明无法到达 i，终点也不可达；否则用 i+nums[i] 更新 farthest。

正确性依据

循环前，[0,farthest] 中每个已扫描位置都可从起点到达。若当前 i<=farthest，从 i 出发可把可达范围扩张到 i+nums[i]，更新后不变量仍成立；若 i>farthest，任何此前位置都无法跨过该缺口，之后位置也不可能到达。扫描完成未失败即终点可达。

样例执行过程

[2,3,1,1,4]：i=0 后边界为 2，i=1 更新为 4，已经覆盖终点。[3,2,1,0,4] 在前四项后边界为 3，到 i=4 时 4>3，返回 false。

代码实现

C++

C++17

#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
    bool canJump(vector<int> nums) {
        int farthest = 0;
        for (int index = 0; index < static_cast<int>(nums.size()); ++index) {
            if (index > farthest) return false;
            farthest = max(farthest, index + nums[index]);
        }
        return true;
    }
};

Python

Python 3

class Solution:
    def canJump(self, nums: list[int]) -> bool:
        farthest = 0
        for index, step in enumerate(nums):
            if index > farthest:
                return False
            farthest = max(farthest, index + step)
        return True

复杂度分析

时间复杂度 O(n)，额外空间 O(1)。

边界与易错点

• 单元素数组已在终点，应返回真。
• 0 不必然失败，只有它出现在当前最远边界之前的缺口位置才失败。
• 不需要真的跳到某个具体位置。

模式迁移

把“最远可达”换成“最远覆盖”，即可处理区间覆盖；要求最少次数时，需要继续记录层边界，见下一题。