LeetCode LCP 09. 最小跳跃次数

Categories:

题目描述
思路分析
1. 解法一：BFS + 指针剪枝（推荐）
相似题目

题目描述

✅ LCP 09. 最小跳跃次数

思路分析

解法一：BFS + 指针剪枝（推荐）

核心思路：

从位置 0 出发，前跳到 i + jump[i]，后跳可到任意 j < i。

用 BFS 保证最短步数，并用指针 next 一次性扩展所有未访问的后跳位置。

当跳出数组即为答案。

复杂度分析：

时间复杂度：O(n)，每个位置最多入队一次。

空间复杂度：O(n)。

import java.util.ArrayDeque;
import java.util.Queue;

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 next = 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 j = next; j < cur; j++) {
                    if (!visited[j]) {
                        visited[j] = true;
                        queue.offer(j);
                    }
                }
                if (cur >= next) {
                    next = cur + 1;
                }
            }
            steps++;
        }

        return -1;
    }
}

func minJump(jump []int) int {
	n := len(jump)
	visited := make([]bool, n)
	queue := make([]int, 0)
	queue = append(queue, 0)
	visited[0] = true

	steps := 0
	next := 1
	for len(queue) > 0 {
		size := len(queue)
		for i := 0; i < size; i++ {
			cur := queue[0]
			queue = queue[1:]

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

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

	return -1
}

相似题目

题目	难度	考察点
45. 跳跃游戏 II	中等	BFS/贪心
55. 跳跃游戏	中等	贪心
1306. 跳跃游戏 III	中等	BFS
1345. 跳跃游戏 IV	困难	BFS
1654. 到家的最少跳跃次数	困难	BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/26597437