跳跃游戏 II 如何用贪心求最少跳跃次数？（LeetCode 45）

简化版

数组 nums[i] 表示从下标 i 最多能往前跳几步，题目保证一定能到终点，求到达最后一个下标的最少跳跃次数。贪心策略：把每一次跳跃看成一层「覆盖区间」，在当前这跳能到达的范围内，选一个能让下一跳延伸得最远的落点。用 curEnd 记录当前这一跳的边界、farthest 记录在这一跳范围内能探到的最远处，每当遍历到 curEnd 就说明必须再跳一次（steps++）并把边界推到 farthest。

详细版

int jump(int[] nums) {
    int steps = 0;        // 已跳次数
    int curEnd = 0;       // 当前这一跳能覆盖的右边界
    int farthest = 0;     // 在当前覆盖范围内，下一跳能到的最远处
    for (int i = 0; i < nums.length - 1; i++) {   // 注意不遍历最后一个
        farthest = Math.max(farthest, i + nums[i]);
        if (i == curEnd) {          // 走到当前跳的边界，必须再跳一步
            steps++;
            curEnd = farthest;      // 新边界 = 这一跳能探到的最远
            if (curEnd >= nums.length - 1) break;  // 已能覆盖终点
        }
    }
    return steps;
}

两个边界变量：curEnd 是「第 steps 跳落地后的覆盖右界」，farthest 是「在 [上一个 curEnd, 当前 curEnd] 里能探到的最远」。
触发跳跃：当 i == curEnd，说明当前这一跳的范围走完了，还没到终点，必须消耗一次跳跃，边界更新为 farthest。
循环到 n-2：遍历不含最后一个下标，避免站在终点还多计一次。
复杂度：O(n) 时间、O(1) 空间。

完整版教学

一、把跳跃看成「一层一层的 BFS」

理解这题最好的模型是 BFS 分层：

第 0 层：只有起点 {0}。
第 1 层：从起点一跳能到的所有点 [1, nums[0]]。
第 2 层：从第 1 层任意点再跳一次能到的所有点……

「最少跳跃次数」= 终点所在的层数。BFS 天然是最短路，所以答案就是终点第一次被覆盖时的层号。贪心做法其实是把这个 BFS 用两个边界变量压成 O(n)，不用真建队列。

二、curEnd 与 farthest 各是什么

curEnd：当前这一跳（第 steps 跳）落地后能覆盖到的最右下标，也就是「当前这一层的右边界」。
farthest：在遍历当前这一层的过程中，不断记录「从这层里任何一点再跳一次，能达到的最远下标」，也就是「下一层的右边界候选」。

遍历时对每个 i 都更新 farthest = max(farthest, i + nums[i])——相当于在当前层里逐个探路，看谁能把下一层推得最远。

三、为什么「走到 curEnd 才 steps++」

关键在触发时机：只有当 i 走到了 curEnd（当前层的右边界），才说明当前这一跳的覆盖范围已经全部探完，而我们还没到终点，于是不得不再跳一次。 此时：

steps++（消耗一次跳跃）；
curEnd = farthest（新的一层边界 = 刚才在这层探到的最远处）。

这保证了每一层只在「探完」时才 +1，且新边界一定是**这一层能延伸的最优（最远）**结果——这正是贪心：不急着跳，先在当前范围内看谁跳得最远，锁定那个最优的下一跳边界。

四、循环为什么到 n-2 结束

写 i < nums.length - 1（不遍历最后一个下标）是一个易错关键点：

如果遍历到最后一个下标 n-1，而恰好 n-1 == curEnd，会触发一次多余的 steps++——但我们已经站在终点，不需要再跳了。
只遍历到 n-2：一旦某次 curEnd 被推到 >= n-1，说明再跳这一步就能到终点，steps 已正确计入，直接结束。

步数只在走到当前层末尾时增加。终点下标无需再向外扩展；若循环处理到 n-1，终点恰好等于 curEnd 时会多记一次“从终点再跳”的不存在动作。

五、贪心正确性：为什么不必枚举落点

有人怀疑：当前层里有很多落点，为什么只记「能延伸最远的」就够，不用逐个尝试？

因为下一层的覆盖范围是 [curEnd+1, farthest] 这样一个连续区间（可达区间无空洞，理由同跳跃游戏 I）。既然下一层能覆盖到的最远点是 farthest，那么 farthest 之内的所有点这一跳都能到——我们只需知道「下一层的右边界能到多远」，具体从当前层哪个点跳过去无所谓。所以维护 farthest 一个量就够，贪心成立。

对照跳跃游戏 I：那题只问「能否到达」，维护一个 farthest 判断覆盖；这题问「最少几跳」，多维护一个 curEnd 来数层数。同一套「覆盖范围」思想，一个数边界、一个数层。

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

本题每一步选择是：把当前一步能覆盖的区间视为 BFS 一层，扫描层内位置更新下一层最远边界，走到 curEnd 才增加步数。

正确性不能只靠直觉，核心证明是：在当前层结束前比较了所有落点的后继覆盖，选择最远边界等价于 BFS 用一层扩展全部节点。这说明任意最优方案都能调整为包含当前贪心选择的方案，且目标值不会变差。

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

数字推演：[2,3,1,1,4] 第一层 [0,0] 扩到2，第二层扫描1、2扩到4，共2跳。

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

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

实现边界是：经典题保证可达；循环只到 n-2，避免到终点后多加一步；不可达版本需检测 farthest==curEnd。

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

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

八、常见误区与追问

误区：每次直接跳到能到的最远下标。 最远落点后续能力可能差；应比较当前层所有位置的覆盖。
误区：扫描每个下标都 steps++。 只有到达当前层边界才完成一次跳跃。
误区：循环必须处理 n-1。 会在终点边界额外计步。
追问：curEnd 与 farthest 区别？ 前者是当前步覆盖边界，后者是下一步候选边界。
追问：为什么是最少步数？ 逐层扩展与无权图 BFS 相同，首次覆盖终点层数最小。
追问：输入不可达怎么办？ 层结束时 farthest 未超过 curEnd 即无法继续。

九、加强记忆

跳跃游戏 II（最少跳数）= 贪心 + BFS 分层思想：farthest 记录当前层里下一跳能探到的最远处，curEnd 是当前层右边界；遍历中不断更新 farthest，每当 i == curEnd 就 steps++ 并把 curEnd 推到 farthest（当前层探完、被迫再跳一次，且跳向最优的最远边界）。循环只到 n-2 防止在终点多计一次。答案即终点所在 BFS 层数，O(n) 时间 O(1) 空间。

简化版

详细版