LeetCode 55. 跳跃游戏

2026-04-18 HGNULB 约 4 分钟

文章信息 19 个分类 4 个标签

分类

LeetCode CodeTop 中等已解决需复习 50-100 字节跳动微软美团阿里巴巴快手腾讯百度滴滴京东华为拼多多 LeetCode 热题 100 面试经典 150 题

题目描述

✅ 55. 跳跃游戏

题意分析

输入是非负整数数组 nums，站在下标 i 时最多能向右跳 nums[i] 步——「最多」意味着可以少跳甚至不跳，落点可以是 i+1 到 i+nums[i] 之间的任意位置。问题只问「能否到达最后一个下标」，不要求给出路径，也不要求跳跃次数最少。

约束上 nums[i] 可以为 0，0 是唯一可能造成「卡死」的元素，但它是否致命，取决于前面的位置能否直接越过它。

边界信号：数组长度至少为 1，起点即终点时不需要任何跳跃，天然可达。

解法：贪心维护最远可达下标

核心思路

问题关键：只需要判断能否到达终点，不要求具体路径或最少跳数。用 DP 标记每个位置、再逐个传播可达范围会重复扫描区间，最坏是 $O(n^2)$。

为什么选贪心：从可达位置 i 可以跳到 i+1 至 i+nums[i]，所以已知可达位置覆盖的是一段连续前缀。无需保存整张布尔数组，只需维护这段前缀的右端点 maxReach。

不变量：处理下标 i 前，maxReach 是所有已确认可达位置能到达的最远下标。只有当 i <= maxReach 时，当前位置才可达，才能用 i + nums[i] 扩展边界；若 i > maxReach，说明可达前缀已经中断，之后的位置也无法参与扩展，可以立即返回 false。当 maxReach >= n - 1 时，终点已经进入可达前缀。

解题步骤

初始化 maxReach = 0，表示起点天然可达。

从左到右遍历下标 i；若 i > maxReach，当前位置不可达，返回 false。

当前位置可达时，用 maxReach = max(maxReach, i + nums[i]) 扩展最远边界。

若边界已经覆盖 n - 1，提前返回 true。

成功例 [2,3,1,1,4]：下标 0 将边界扩到 2，下标 1 再扩到 4，覆盖终点。失败例 [3,2,1,0,4]：边界最多到 3，扫描到下标 4 时出现 4 > maxReach，因此不可达。

代码实现

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]);
            if (maxReach >= nums.length - 1) {
                return true;
            }
        }
        return true;
    }
}

func canJump(nums []int) bool {
    maxReach := 0
    for i := 0; i < len(nums); i++ {
        if i > maxReach {
            return false
        }

        reach := i + nums[i]
        if reach > maxReach {
            maxReach = reach
        }
        if maxReach >= len(nums)-1 {
            return true
        }
    }
    return true
}

复杂度分析

时间复杂度：$O(n)$，每个下标最多访问一次。

空间复杂度：$O(1)$，只维护最远可达边界。

关键点总结

可达集合是连续前缀，因此一维边界足以替代整张 DP 表。

更新顺序必须是“先确认当前位置可达，再用它扩展边界”。

本题只问可达性；若追问最少跳数，需要像 45 题那样额外维护当前跳跃边界并分层计步。

易错点总结

必须先判断 i > maxReach。反例 [3,2,1,0,4]：若让不可达的下标 4 参与更新，会错误地把边界扩到 8。

不能见到 0 就失败；[2,0,1] 可以从下标 0 直接越过 0。

不可达条件是 i > maxReach，不是 i >= maxReach；边界位置本身仍然可达。

更新要取最大值，不能直接赋值为 i + nums[i]，否则较弱的后续位置可能让边界倒退。

单元素数组 [0] 起点就是终点，应返回 true。

相似题目

题目	难度	考察点
45. 跳跃游戏 II	中等	在可达前提下求最少跳数，按边界分段计步的贪心
1306. 跳跃游戏 III	中等	可左右双向跳，可达范围不再是连续前缀，需 BFS/DFS
1345. 跳跃游戏 IV	困难	增加等值传送边求最短步数，BFS 分层加同值桶优化
134. 加油站	中等	环形路线的贪心可行性，靠总盈亏与起点重置论证