LeetCode LCP 09. 最小跳跃次数

约 6 分钟
文章信息 9 个分类 5 个标签
分类
LeetCode CodeTop 困难 未解决 2-5 字节 拼多多 网易 快手
标签
数组 动态规划 广度优先搜索 线段树 LCP

题目描述

✅ LCP 09. 最小跳跃次数

image-20260928225505009

题意分析

从下标零的弹簧出发，每次可以向右跳到固定位置 i + jump[i]，也可以向左跳到任意一个更小的有效下标。一次向左跳无论跨过多远，都只算按动一次弹簧。

目标是向右越过数组末尾，求最少跳跃次数。左跳只能落在机器内已有的弹簧上，不能从左端跳出机器；右跳必须使用当前位置规定的完整距离，不能自行选择较短的距离。

解法：BFS + 左跳区间去重

核心思路

[!blue]

把每个下标看作一个状态，每次合法跳跃看作一条代价为一的边。所有边代价相同，用 BFS 按已用跳数逐层处理，第一次发现能够向右跳出的位置，就能得到最少次数。层数 steps 表示到达当前层位置已经跳了多少次，真正离开还需要再跳一次。

每个位置只有一个右跳目标，可以直接判断是否越界或已访问。左跳却能到达全部更小下标，若每次都从零重新扫描，虽然入队会去重，扫描本身仍可能达到平方时间。

用 nextUnvisitedLeft 维护一个单调向右的前缀边界：它之前的下标都已经被发现，不必再作为新增左跳候选扫描。处理 cur 时，只扫描 [nextUnvisitedLeft, cur)；遇到尚未访问的位置就标记并入队。cur 本身也已经访问，所以处理完后，边界可以推进到至少 cur + 1。

这个名字不代表边界之后的所有位置都未访问；右跳可能提前到达很靠右的位置，所以扫描新区间时仍要查 visited。反过来，BFS 保证任何已发现位置的距离已经最短，后续从其他位置重复跳到它不会改善答案，跳过已覆盖前缀不会漏掉更短路径。

队列按距离出队，不保证下标递增。遇到比当前边界小的 cur 时不再扫描，也不能把边界退回去。这样每个下标至多进入一次左跳扫描区间，每个状态也只入队一次，隐式的大量左跳边就被压缩为总共线性的处理。

解题步骤

  1. 将位置零入队并标记，初始化 steps = 0、前缀扫描边界为一。
  2. 固定本层队列长度，只处理当前已经在队列中的这一层节点。
  3. 对位置 cur 计算右跳目标，若到达或越过 n，返回 steps + 1；否则将未访问的右跳目标入队。
  4. 从当前扫描边界到 cur - 1 枚举新增左跳候选，将未访问位置入队，并只向右推进扫描边界。
  5. 本层全部处理完，将 steps 加一，继续下一层。

代码实现

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) {
                    // 到当前位置已经走了 steps 步，跳出机器还要一步。
                    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 {
                // 到当前位置已经走了 steps 步，跳出机器还要一步。
                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)$。每个位置至多入队出队一次，右跳只检查一个目标；左侧扫描边界单调前进，全部左跳候选合计最多扫描线性次。
  • 空间复杂度：$O(n)$，保存访问标记和 BFS 队列，不显式建立可能含平方数量边的邻接表。

关键点总结

[!green]

  • 同等跳跃代价适合 BFS，按层首次发现跳出边界就得到最短距离。
  • 访问表避免重复入队，单调前缀边界避免重复扫描，两者解决不同的重复工作。
  • 边界之前全部已发现，边界之后仍可能存在由右跳提前发现的位置。
  • 队列距离有序不代表下标有序，扫描边界必须保持只增不减。

易错点总结

[!yellow]

  • 每次从零扫描所有左侧位置，即使不重复入队，也会重复检查大量下标，退化为平方时间。
  • 用较小的出队下标直接重置边界，会让已经处理的前缀被反复扫描。
  • 左跳候选不检查访问标记，可能与此前右跳发现的位置重复入队。
  • 把当前层新加入的节点立即作为同层处理，会把多次跳跃错误算成一次；应固定本层大小。
  • 到达可跳出的位置时直接返回 steps，会漏算真正跳出机器的最后一步。

相似题目

题目 难度 关联与区别
1345. 跳跃游戏 IV 困难 同样存在大量隐式邻居，向左可达区间一旦整体扫过就应避免重复展开，以免退化平方级。
1306. 跳跃游戏 III 中等 原题左右跳长都由当前位置决定，本题左跳可选任意较小下标，且目标是跳出数组。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/26597437
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！