LeetCode LCP 09. 最小跳跃次数

2026-01-30 HGNULB 约 14 分钟

文章信息 9 个分类 5 个标签

分类

题目描述

✅ LCP 09. 最小跳跃次数

题意分析

一排编号 0 到 $n-1$ 的弹簧，小球初始在 0 号位置。在位置 i 时有两种操作，每种都算一次：向右弹射到 i + jump[i]，若这个位置大于等于 $n$ 则小球飞出机器；向左移动到任意一个编号严格小于 i 的位置。求把小球弹出机器所需的最少操作次数。

要什么：最少操作次数。每次操作代价都是 1，无论是右弹一大步还是左移一大段。代价一致就意味着这是无权图上的最短路，BFS 是标准工具——千万不要被「跳跃」二字带去贪心，因为左移是自由的，贪心的局部最优在这里完全站不住脚。

建模：节点是位置 $0 \dots n-1$，外加一个虚拟的「已飞出」终点。从 i 出发的边有两类——一条指向 i + jump[i]（或指向终点），以及 $i - 1$ 条分别指向 $0, 1, \dots, i-1$。问的是从 0 到终点的最短边数。

这里立刻能看出本题的独特难点：左移边的数量是 $O(n^2)$ 级的。若老老实实按 BFS 模板对每个出队的 i 枚举全部 $j < i$，光是遍历边就要 $O(n^2)$，$n$ 达到 $10^6$ 时彻底不可行。所以这道题真正考的不是 BFS 本身，而是如何在不显式遍历所有左移边的前提下保持 BFS 的正确性。

约束透露的信号：$n$ 最大 $10^6$，jump[i] 至少为 1。$10^6$ 这个规模明确要求 $O(n)$ 或 $O(n \log n)$；jump[i] >= 1 保证了右弹一定会前进，不会原地打转，从而保证解一定存在（最坏情况下一路右弹总能飞出去）。

边界：$n = 1$ 时从 0 号位一次右弹（0 + jump[0] >= 1）即可飞出，答案是 1；答案至少是 1，不可能是 0；小球起点是 0，而左移的目标必须严格小于当前位置，所以位置 0 永远不可能被再次到达（也没有必要）。

解法：BFS + 左跳区间去重

核心思路

先确认为什么必须 BFS 而不是贪心或 DP。贪心失效是因为「向左移动」这个操作让状态可以自由回退，无法定义一个单调推进的局部最优；朴素 DP 也麻烦，因为 dp[i] 既依赖左边又依赖右边，转移带环。而每步代价恒为 1 这一点，把它牢牢钉在无权最短路上，BFS 按层扩散天然给出最优解。

于是问题只剩下效率。朴素 BFS 的致命伤在于：出队一个位置 i 时要把 $0 \dots i-1$ 全部检查一遍看有没有没访问过的。若队列里陆续出现很多较大的下标，这段区间会被反复扫描，总代价 $O(n^2)$。

但仔细看：被重复扫描的那些位置，其实早就已经被访问过了。真正需要新入队的只有「从未被任何左移覆盖过」的那些位置。而这些位置有一个极好的性质——它们总是连续的一段前缀之外的部分。

严格地说，引入一个指针 nextUnvisitedLeft，含义是：

所有编号严格小于 nextUnvisitedLeft 的位置都已经被访问并入队过了。

这个不变量是整个优化的支点。有了它，出队位置 cur 时的左移扩展只需扫描区间 $[\,\text{nextUnvisitedLeft},\ cur\,)$ —— 更左边的部分由不变量保证已被处理，无需重扫。扫完之后，$[0, cur]$ 全部已访问（区间内的刚被处理、cur 自己是出队的必然已访问），于是把指针推进到 cur + 1。

指针只增不减，而每个位置只会在指针推进的过程中被扫描一次，所有左移扩展的总代价因此被摊成 $O(n)$，而不是每次 $O(n)$。这与滑动窗口里「左指针单调不减所以内层循环总量有界」是同一种均摊论证。

还有一个细节：cur 出队的顺序不保证单调递增，可能出现 cur < nextUnvisitedLeft 的情况（这个位置及其左边早就被覆盖了）。此时扫描区间为空、循环不执行，而指针推进也必须加上 if (cur >= nextUnvisitedLeft) 的保护——否则会把指针往回拨，破坏不变量并导致重复扫描。

右移则简单得多：每个位置只有唯一的右弹目标 cur + jump[cur]。若它越界，说明再花一次操作就能飞出，答案是 steps + 1（steps 是走到 cur 所花的次数，飞出还要再算一次）；否则按常规入队。因为 BFS 按层扩散，第一次出现越界的那一刻必然对应最少操作数。

最后是分层写法：每轮先取队列长度快照，把这一整层出完再 steps++。不变量是「第 steps 层出队的位置，从起点走到它恰好用了 steps 次操作」。

访问标记一律在入队时打，无论是右弹目标还是左移目标。这既保证每个位置只入队一次（总入队量 $O(n)$），也是 nextUnvisitedLeft 不变量成立的前提。

解题步骤

开长度 n 的 visited 数组与队列，把 0 入队并标记；steps = 0，nextUnvisitedLeft = 1。为什么指针初值是 1 而不是 0：位置 0 是起点，已经被访问，所以「所有小于 1 的位置都已访问」在初始时就成立。写成 0 会让第一次左移扫描重新考察位置 0，虽然 visited[0] 为真不会重复入队，但破坏了不变量的表述统一性。

外层每轮先取 size = queue.size() 的快照。为什么：内层会往队列追加下一层的位置，直接用 queue.size() 作条件会让层边界消失，steps 与操作次数的对应关系随之失效。

出队 cur，先算 forward = cur + jump[cur]。为什么右弹要先处理：它是唯一可能直接产出答案的分支，早判早返回；也让越界这个终止条件的位置在代码里一目了然。

若 forward >= n，立即返回 steps + 1。为什么加一：steps 是「走到 cur 所用的操作数」，从 cur 弹出去还要再花一次。这是本题最容易差一位的地方。为什么第一次越界就是最优：BFS 保证 cur 处在最小的可能层数上，任何更早飞出的方案都会在更前面的层被发现。

否则若 forward 未访问，标记并入队。为什么要判未访问：同一个位置可能被多个前驱指向，重复入队会让队列膨胀且层数统计混乱。

扫描 left 从 nextUnvisitedLeft 到 cur - 1，未访问的标记并入队。为什么起点是 nextUnvisitedLeft 而不是 0：由不变量，更左边的位置全部已访问，重扫纯属浪费，且正是 $O(n^2)$ 的来源。为什么终点是 cur 的前一个：左移要求目标编号严格小于当前位置。

若 cur >= nextUnvisitedLeft，把指针推进到 cur + 1。为什么要加这个条件：cur 可能小于当前指针（它早已被覆盖），此时推进会让指针倒退，不变量被破坏。为什么推进后不变量仍成立：扫描已经覆盖了 $[\text{旧指针}, cur)$，而 cur 自身作为出队元素必然已访问，故 $[0, cur]$ 全已访问。

一层处理完 steps++；队列耗尽返回 -1。为什么实际不会走到 -1：jump[i] >= 1 保证右弹总在前进，从任何位置一路右弹都能在有限步内越界，所以解必然存在；这一行只是防御性兜底。

以 具体用例 jump = [2, 5, 1, 1, 1, 1]（$n = 6$）走一遍，预期答案是 3。

初始化：visited = [T,F,F,F,F,F]，队列 [0]，steps = 0，nextUnvisitedLeft = 1。

第 0 层（size = 1，此层位置的操作数为 0）：
出队 cur = 0。右弹 forward = 0 + jump[0] = 2，未越界（$2 < 6$），visited[2] = true，入队。
左移扫描 left 从 1 到 < 0——区间为空，不执行。这符合直觉：位置 0 左边没有任何位置可去。
指针推进检查：cur = 0 >= nextUnvisitedLeft = 1 不成立，指针保持 1。这里正是保护条件在起作用——若无条件推进，指针会被拨回 1（恰好相同，本例无害），但在一般情形下会造成倒退。
本层结束，steps 变成 1。队列 [2]。

第 1 层（size = 1，操作数为 1）：
出队 cur = 2。右弹 forward = 2 + jump[2] = 3，未越界，visited[3] = true，入队。
左移扫描 left 从 nextUnvisitedLeft = 1 到 < 2，即只有 left = 1：未访问，visited[1] = true，入队。注意扫描没有从 0 开始——位置 0 由不变量保证已访问，跳过它是本题优化的核心体现。
指针推进：cur = 2 >= 1 成立，nextUnvisitedLeft = 3。此刻 $[0,2]$ 确实全部已访问。
本层结束，steps 变成 2。队列 [3, 1]。

第 2 层（size = 2，操作数为 2）：
出队 cur = 3。右弹 forward = 3 + jump[3] = 4，未越界，visited[4] = true，入队。左移扫描 left 从 3 到 < 3，区间为空——因为 $[0,2]$ 已全部访问，无需重扫，这正是均摊 $O(n)$ 的来源。指针推进：3 >= 3 成立，nextUnvisitedLeft = 4。
出队 cur = 1。右弹 forward = 1 + jump[1] = 1 + 5 = 6，越界（$6 \ge 6$），返回 steps + 1 = 2 + 1 = 3。

答案 3。还原路径：位置 0 右弹到 2（第 1 次操作），从 2 左移到 1（第 2 次操作），从 1 右弹到 6 飞出（第 3 次操作）。核对 steps 的含义：出队 cur = 1 时处在第 2 层，说明走到位置 1 用了 2 次操作，再加飞出的那一次共 3 次，与 steps + 1 完全对应。

顺带看一眼若不加 nextUnvisitedLeft 会怎样：出队 cur = 3 时要从 0 扫到 2，出队 cur = 4 时要从 0 扫到 3……在 $n = 10^6$ 且队列里出现大量大下标的数据上，重复扫描的总量逼近 $n^2 / 2 = 5 \times 10^{11}$，必然超时。而有了指针，每个位置终生只被扫描一次。

代码实现

class Solution {
    // 右跳是单个确定位置，左跳会到达大量未访问下标。
    public int minJump(int[] jump) {
        int n = jump.length;
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new ArrayDeque<>();

        queue.offer(0);
        visited[0] = true;

        int steps = 0;
        int nextUnvisitedLeft = 1;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int cur = queue.poll();
                int forward = cur + jump[cur];

                if (forward >= n) {
                    return steps + 1;
                }
                if (!visited[forward]) {
                    visited[forward] = true;
                    queue.offer(forward);
                }

                for (int left = nextUnvisitedLeft; left < cur; left++) {
                    if (!visited[left]) {
                        visited[left] = true;
                        queue.offer(left);
                    }
                }

                if (cur >= nextUnvisitedLeft) {
                    nextUnvisitedLeft = cur + 1;
                }
            }
            steps++;
        }

        return -1;
    }
}

func minJump(jump []int) int {
    // 右跳是单个确定位置，左跳会到达大量未访问下标。
    n := len(jump)
    visited := make([]bool, n)
    queue := make([]int, 0, n)
    visited[0] = true
    queue = append(queue, 0)

    steps := 0
    nextUnvisitedLeft := 1
    head := 0

    for head < len(queue) {
        size := len(queue) - head
        for i := 0; i < size; i++ {
            cur := queue[head]
            head++

            forward := cur + jump[cur]
            if forward >= n {
                return steps + 1
            }
            if !visited[forward] {
                visited[forward] = true
                queue = append(queue, forward)
            }

            for left := nextUnvisitedLeft; left < cur; left++ {
                if !visited[left] {
                    visited[left] = true
                    queue = append(queue, left)
                }
            }
            if cur >= nextUnvisitedLeft {
                nextUnvisitedLeft = cur + 1
            }
        }
        steps++
    }

    return -1
}

复杂度分析

时间复杂度：$O(n)$。凭什么：每个位置至多入队一次、出队一次（入队瞬间就打访问标记），出队时的右弹处理是常数；左移扫描看似是内层循环，但扫描区间的左端点 nextUnvisitedLeft 单调不减且上界为 $n$，因此整个算法生命周期内左移扫描的总步数不超过 $n$，均摊到每次出队是 $O(1)$。这是典型的摊还分析——形式上双层嵌套，实质上是两个各走一遍的指针。若去掉这个指针，最坏退化到 $O(n^2)$，$n = 10^6$ 时无法通过。

空间复杂度：$O(n)$。凭什么：visited 数组固定 $n$ 个布尔值；队列在最坏情况下会同时容纳 $O(n)$ 个位置。没有递归，不存在栈溢出风险——这在 $n = 10^6$ 的规模下是必须的，DFS 式写法会直接爆栈。

关键点总结

每步代价相同的「最少操作数」一律先想 BFS，哪怕操作的「跨度」差异很大。本题里右弹一步可能跨越几十万个位置、左移一步也能回退任意远，但它们的代价都是 1，所以在图上就是等权边。跨度大小与边权无关，这一点必须分清。

边数是 $O(n^2)$ 时，不要遍历边，要遍历「尚未被覆盖的节点」。这是本题最值钱的思想：左移边虽多，但它们指向的目标集合是一个前缀，用一个单调指针记录「前缀边界」，就能保证每个节点只被考察一次。同类技巧在 1345（同值下标互相可达，用完即清空桶）里以另一种面貌出现。

单调指针的均摊分析要能说出口：指针只增不减、上界为 $n$，所以内层循环的总执行次数有界。面试中被问「这不是双层循环吗，为什么是 $O(n)$」时，这句话就是答案。

不变量要写成一句可验证的断言：「所有编号小于 nextUnvisitedLeft 的位置都已访问并入队」。有了它，「扫描区间为什么可以从指针开始」和「指针为什么可以推进到 cur + 1」都变成一行推导。

指针推进必须加 cur >= nextUnvisitedLeft 的保护。BFS 的出队顺序不保证下标单调，无条件赋值会让指针倒退，不变量崩塌，重复扫描随之而来。

越界时返回 steps + 1 而非 steps。判断「我数的是走到当前位置的操作数，还是包含最后一跳的总数」，是这类计数题的通用自检。

访问标记在入队时打，右弹目标与左移目标一视同仁。这既保证总入队量 $O(n)$，也是指针不变量成立的前提。

面试视角：这题被问到时，先给出「BFS 求无权最短路」的建模，紧接着主动指出「左移边有 $O(n^2)$ 条，朴素 BFS 会超时」——能自己发现这个瓶颈，比会写 BFS 模板重要得多。然后引入单调指针并说清不变量与均摊分析。面试官常见追问是「能不能用 DP 或线段树」——可以：设 dp[i] 为从 i 出发飞出的最少次数，从右往左递推，dp[i] = min(dp[i + jump[i]], 1 + min(dp[j]) for j > i)，用线段树或后缀最小值维护区间最小，复杂度 $O(n \log n)$ 或 $O(n)$；能把这条替代路线也讲清楚，说明你理解的是问题结构而非某一个模板。

易错点总结

错误写法：越界时返回 steps 而不是 steps + 1 → 用例 jump = [2,5,1,1,1,1]，出队 cur = 1 时 steps = 2，返回 2；正确答案是 3。steps 只统计了走到 cur 的操作数，从 cur 飞出还要再算一次。

错误写法：左移扫描每次都从 0 开始（不用 nextUnvisitedLeft） → 用例是 $n = 10^6$ 且队列中陆续出现大下标时，重复扫描总量接近 $5 \times 10^{11}$ 次，稳定超时。逻辑虽正确，但完全没有解决本题真正的难点。

错误写法：指针推进不加保护，直接写 nextUnvisitedLeft = cur + 1 → 用例 jump = [3,1,1,1,1,1]，若某一层先出队大下标 4 把指针推到 5、随后出队小下标 1 又把指针拨回 2，则 $[2,4]$ 这段会被后续位置重复扫描，复杂度退化，且指针语义不再可信。

错误写法：左移扫描写成 for (int left = nextUnvisitedLeft; left <= cur; left++) → 用例任意，会把 cur 自己也纳入扫描；虽然 visited[cur] 为真不会重复入队，但一旦扫描逻辑改成无条件入队就会自环。左移要求目标严格小于当前位置。

错误写法：出队时才打访问标记 → 用例 jump = [2,1,1,1]，同一个位置可能从右弹与左移两条路径重复入队，队列膨胀；更严重的是 nextUnvisitedLeft 的不变量依赖「扫过即已访问」，出队才标记会让不变量失效，导致某些位置被跳过而漏解。

错误写法：外层写 for (int i = 0; i < queue.size(); i++)（不取快照） → 用例 jump = [2,5,1,1,1,1]，本层扩展出的新位置混入当前层，steps 不再等于操作数，返回值偏小。

错误写法：nextUnvisitedLeft 初值设为 0 → 用例 jump = [2,5,1,1,1,1]，第一次左移扫描会重新考察位置 0；虽然 visited[0] 为真不至于出错，但若把扫描体误写成无条件入队，起点会被再次加入队列，层数统计立刻错乱。初值 1 才与「小于它的都已访问」这一语义严格对应。

错误写法：用贪心，每次尽量往右弹、弹不出去就回退一格 → 用例 jump = [2,5,1,1,1,1]，贪心从 0 弹到 2、再弹到 3、4、5，然后一路右弹到 6 飞出共 5 次；正确答案是 3（先弹到 2，再左移到 1，从 1 一次飞出）。左移可以任意远，局部最优不成立。

错误写法：用 DFS 递归代替 BFS → 用例 $n = 10^6$ 时递归深度可达百万级，直接栈溢出；即便不溢出，DFS 找到的第一条路径也不保证最短。

错误写法：右弹目标不判 visited 就入队 → 用例 jump = [1,1,1,1]，多个位置可能弹向同一目标，重复入队导致同一位置在不同层被处理，操作数统计出错且队列规模失控。

错误写法：Go 中用 queue = queue[1:] 出队却仍用 len(queue) 计算本层大小 → 切片头指针推进后长度随之缩短，与「本层还剩多少个」的语义不符，层边界错乱；应像本文这样用 head 下标推进并以 len(queue) - head 计算剩余量。

相似题目

题目	难度	考察点
1345. 跳跃游戏 IV	困难	同样面临 $O(n^2)$ 的隐式边（同值下标两两可达），靠「用完即清空该值的桶」去重
1654. 到家的最少跳跃次数	中等	状态要额外记录「上一步是否向后跳」，且搜索上界需要自己论证
773. 滑动谜题	困难	节点是整块棋盘的排列，需要状态压缩成字符串才能判重
752. 打开转盘锁	中等	每个状态有固定的 8 个后继，边数可控，是不需要去重优化的标准 BFS
127. 单词接龙	困难	邻接关系需要按通配模式建桶构造，同样是「边太多所以不显式建图」的思路
909. 蛇梯棋	中等	转移是掷骰子的六个分支，难点在蛇形编号与二维坐标的换算
1293. 网格中的最短路径	困难	状态需要多带一维「剩余可消除障碍数」，展示了状态设计而非边去重的另一类难点
994. 腐烂的橘子	中等	多源 BFS 的基础形态，边数天然 $O(n)$，适合对照理解分层写法