LeetCode 45. 跳跃游戏 II

Categories:

Tags:

题目描述
思路分析
1. 解法一：贪心（推荐）
2. 解法二：动态规划
相似题目

题目描述

✅ 45. 跳跃游戏 II

思路分析

解法一：贪心（推荐）

核心思路：

维护当前跳跃能到达的最远边界 curEnd 和遍历过程中能到达的最远位置 farthest

遍历数组时，不断更新 farthest = max(farthest, i + nums[i])

当遍历到 curEnd 时，说明必须跳一次，跳跃次数加 1，并将 curEnd 更新为 farthest

由于最后一个位置不需要再跳，遍历到 n - 2 即可

复杂度分析：

时间复杂度：O(n)，其中 n 为数组长度，只需一次线性遍历

空间复杂度：O(1)，只使用常数级别的额外空间

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        // 记录跳跃次数
        int jumps = 0;
        // 当前跳跃能到达的边界
        int curEnd = 0;
        // 遍历过程中能到达的最远位置
        int farthest = 0;

        // 不需要跳到最后一个位置，遍历到 n-2
        for (int i = 0; i < n - 1; i++) {
            // 更新在当前范围内能到达的最远位置
            farthest = Math.max(farthest, i + nums[i]);

            // 到达当前跳跃的边界，必须跳一次
            if (i == curEnd) {
                jumps++;
                // 更新跳跃边界为最远可达位置
                curEnd = farthest;
            }
        }
        return jumps;
    }
}

func jump(nums []int) int {
    n := len(nums)
    // 记录跳跃次数
    jumps := 0
    // 当前跳跃能到达的边界
    curEnd := 0
    // 遍历过程中能到达的最远位置
    farthest := 0

    // 不需要跳到最后一个位置，遍历到 n-2
    for i := 0; i < n-1; i++ {
        // 更新在当前范围内能到达的最远位置
        if i+nums[i] > farthest {
            farthest = i + nums[i]
        }

        // 到达当前跳跃的边界，必须跳一次
        if i == curEnd {
            jumps++
            // 更新跳跃边界为最远可达位置
            curEnd = farthest
        }
    }
    return jumps
}

解法二：动态规划

核心思路：

定义 dp[i] 为到达位置 i 所需的最少跳跃次数

初始化 dp[0] = 0，其余位置初始化为正无穷

对于每个位置 i，遍历其能跳到的所有位置 j（i < j <= i + nums[i]），更新 dp[j] = min(dp[j], dp[i] + 1)

此解法适合理解题意，但时间复杂度较高，不推荐用于面试

复杂度分析：

时间复杂度：O(n²)，其中 n 为数组长度，双重循环遍历

空间复杂度：O(n)，需要额外的 dp 数组

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        // dp[i] 表示到达位置 i 的最少跳跃次数
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int i = 0; i < n; i++) {
            if (dp[i] == Integer.MAX_VALUE) {
                continue;
            }
            // 从位置 i 出发，更新所有可达位置的最小跳跃次数
            int maxReach = Math.min(i + nums[i], n - 1);
            for (int j = i + 1; j <= maxReach; j++) {
                dp[j] = Math.min(dp[j], dp[i] + 1);
            }
        }
        return dp[n - 1];
    }
}

func jump(nums []int) int {
    n := len(nums)
    // dp[i] 表示到达位置 i 的最少跳跃次数
    dp := make([]int, n)
    for i := range dp {
        dp[i] = math.MaxInt32
    }
    dp[0] = 0

    for i := 0; i < n; i++ {
        if dp[i] == math.MaxInt32 {
            continue
        }
        // 从位置 i 出发，更新所有可达位置的最小跳跃次数
        maxReach := i + nums[i]
        if maxReach > n-1 {
            maxReach = n - 1
        }
        for j := i + 1; j <= maxReach; j++ {
            if dp[i]+1 < dp[j] {
                dp[j] = dp[i] + 1
            }
        }
    }
    return dp[n-1]
}

相似题目

题目	难度	考察点
55. 跳跃游戏	中等	贪心
1306. 跳跃游戏 III	中等	BFS / DFS
1345. 跳跃游戏 IV	困难	BFS
1696. 跳跃游戏 VI	中等	动态规划 + 单调队列
1871. 跳跃游戏 VII	中等	BFS + 前缀和
134. 加油站	中等	贪心
763. 划分字母区间	中等	贪心

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/32532865