跳跃游戏能否到达终点？如何用贪心判断？（LeetCode 55）

简化版

给一个非负整数数组 nums，你站在下标 0，nums[i] 表示从 i 最多能往前跳几步。问能否到达最后一个下标。贪心策略：维护「当前能到达的最远下标 farthest」，从左往右扫，只要当前下标 i 在可达范围内（i <= farthest），就用 i + nums[i] 更新 farthest；一旦 farthest 覆盖到末尾就返回 true，若扫描中出现 i > farthest（跳不到 i）则返回 false。

详细版

boolean canJump(int[] nums) {
    int farthest = 0;                       // 当前能到达的最远下标
    for (int i = 0; i < nums.length; i++) {
        if (i > farthest) return false;     // 当前位置都到不了，后面更别想
        farthest = Math.max(farthest, i + nums[i]);   // 用 i 更新最远可达
        if (farthest >= nums.length - 1) return true; // 已能覆盖终点
    }
    return true;
}

状态：farthest = 到目前为止，站在 [0, i] 内任意可达位置能跳到的最远下标。
可达性判断：遍历到 i 时若 i > farthest，说明前面所有跳跃都无法覆盖 i，i 及之后全部不可达 → false。
提前返回：farthest >= n-1 时立刻 true。
复杂度：O(n) 时间、O(1) 空间。

完整版教学

一、别陷进「枚举每一种跳法」的坑

新手容易想成搜索/DP：dp[i] 表示能否到达 i，然后 dp[i] = 任意 j<i 且 dp[j] 且 j+nums[j]>=i。这是 O(n²) 的，能过但不优。这道题的精髓是：我们根本不关心「怎么跳到」某个位置，只关心「最远能覆盖到哪」。 只要终点落在覆盖范围内，就一定有办法跳过去。

二、核心量：farthest（当前最远可达）

定义 farthest = 从起点出发，用已经遍历过的这些位置，最远能蹦到的下标。它是一个「覆盖范围的右边界」。

关键洞察：如果下标 i 是可达的（i <= farthest），那么站在 i 上，我又能把覆盖范围推到 i + nums[i]。 于是我们从左到右扫，每遇到一个可达的 i，就尝试用它把 farthest 往右扩：

farthest = max(farthest, i + nums[i])

只要 farthest 单调地被推到 >= n-1，终点就进入了覆盖范围，返回 true。

三、什么时候判定「到不了」

遍历到 i 时，如果发现 i > farthest，意味着：目前累积的最大覆盖范围都够不着 i。既然 i 都到不了，i 之后（下标更大）就更到不了了——因为跳跃只能往右，且必须先站上某个可达点才能继续。此时直接返回 false。

换个角度：farthest 就像水位，i 就像你要踩的石头。水位（覆盖范围）没漫到石头 i，你就踩不上去，游戏结束。

四、贪心为什么正确

贪心选择性质在这里体现为：我们不需要知道到达 i 的「具体路径」，只需要知道 i「是否可达」以及「从 i 出发能延伸多远」。因为：

可达性有传递性且只依赖覆盖范围：[0, farthest] 内所有点都可达，这是一个连续区间（跳跃能覆盖中间所有点，因为 nums[i] 是「最多跳几步」，可以跳 1、2、…、nums[i] 中任意一步，所以中间不留空洞）。
因此维护一个「最远右边界」就完整刻画了「哪些点可达」，无需 DP 记录每个点。

正因为可达区间是连续无空洞的，「能到最远点」⇒「能到中间任意点」，贪心才成立。

五、跳跃游戏 II 的伏笔

本题只问「能不能到」，孪生题 跳跃游戏 II（LeetCode 45）问「最少跳几次到终点」——那题要在每一次跳跃的可达范围内，选一个「下一跳能延伸最远」的落点，用「当前跳的边界 + 下一跳能到的最远边界」双变量贪心。两题都基于同一个「覆盖范围」思想，是连着考的高频对，建议一起掌握。

可达性只关心 farthest 是否覆盖终点；最少跳数还要区分“当前使用几步能覆盖到哪”。因此 II 额外维护 curEnd，把 [上一层末尾+1, curEnd] 看作同一 BFS 层。

六、贪心选择为什么不会堵死未来

本题每一步选择是：扫描所有当前可达位置并维护 farthest；若 i>farthest，当前位置及后面都不可达。

正确性不能只靠直觉，核心证明是：farthest 概括已访问前缀所有跳法能到的最远边界，边界内具体落点无需分别保留。这说明任意最优方案都能调整为包含当前贪心选择的方案，且目标值不会变差。

排序或预处理，建立可比较的选择顺序
维护“当前选择给未来留下的有效边界”
若候选不劣于现有边界，则提交选择并更新状态

数字推演：[2,3,1,1,4] 从前缀最远可达不断扩到4；[3,2,1,0,4] 在 i=4 时超过 farthest=3。

记忆钩子：贪心不是“选眼前最大”，而是选一个能被交换论证证明、对未来最宽松的代表。

七、退化边界、复杂度与反例检查

实现边界是：必须先确认 i 可达再用 nums[i] 扩展；空数组语义按题目；大下标相加需注意溢出。

检查项	必须回答
排序键	为什么按这个维度和方向排序
局部选择	它保留了什么未来可能性
正确性	交换、领先或反证中的哪一种
失败边界	哪个题目条件一改就不能贪心
复杂度	排序成本与扫描成本是否都计入

测试时至少覆盖单元素、全部相等、严格递增/递减、恰好卡在边界、局部最优容易误导的反例。若无法写出交换论证或领先性质，应暂停使用贪心，转而尝试动态规划、搜索或数据结构。

八、常见误区与追问

误区：每一步都跳最大距离即可。 具体落点贪心可能失败，正确做法维护所有可达前缀的最远边界。
误区：可以用不可达位置更新 farthest。 该位置本身到不了，不能贡献跳跃。
误区：遇到 0 一定失败。 若此前 farthest 已越过它就没有影响。
追问：为什么一个 farthest 足够？ 目标只问可达性，较近边界被更远边界支配。
追问：何时提前成功？ farthest≥n-1 时即可返回。
追问：与最少跳数有何不同？ 后者还要维护当前步数覆盖层的右边界。

九、加强记忆

跳跃游戏（能否到达）= 一次遍历维护「最远可达下标 farthest」：扫到 i 若 i > farthest 直接 false（这石头水位没漫到），否则 farthest = max(farthest, i+nums[i])，一旦 farthest >= n-1 就 true。贪心成立的根因是可达区间连续无空洞（nums[i] 是「最多跳几步」，中间点都能落），所以只需盯住覆盖范围的右边界，不必关心具体跳法。O(n) 时间 O(1) 空间。

简化版

详细版