LeetCode 55. 跳跃游戏

Categories:

Tags:

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

题目描述

✅ 55. 跳跃游戏

思路分析

解法一：贪心（推荐）

核心思路：

维护变量 farthest 表示从起点出发，当前所有可达位置中能跳到的最远下标。

遍历每个位置 i，若 i > farthest，说明当前位置不可达（前面所有节点都无法跳到这里），直接返回 false。

否则更新 farthest = max(farthest, i + nums[i])，取当前可达最远处。

若任意时刻 farthest >= n - 1，说明终点可达，返回 true。

贪心正确性：能到达位置 j 则必然能到达 [0, j] 内的所有位置（可停在任意中间节点），因此只需维护最远边界即可覆盖所有可达情况。

复杂度分析：

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

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

class Solution {
    public boolean canJump(int[] nums) {
        // 记录当前能够到达的最远下标
        int farthest = 0;
        for (int i = 0; i < nums.length; i++) {
            // 若当前位置超过最远可达位置，说明无法到达此处
            if (i > farthest) {
                return false;
            }
            // 更新最远可达下标
            farthest = Math.max(farthest, i + nums[i]);
        }
        return true;
    }
}

func canJump(nums []int) bool {
	// 记录当前能够到达的最远下标
	farthest := 0
	for i := 0; i < len(nums); i++ {
		// 若当前位置超过最远可达位置，说明无法到达此处
		if i > farthest {
			return false
		}
		// 更新最远可达下标
		if i+nums[i] > farthest {
			farthest = i + nums[i]
		}
		// 最远可达位置已覆盖终点，提前返回
		if farthest >= len(nums)-1 {
			return true
		}
	}
	return false
}

解法二：动态规划

核心思路：

定义 dp[i] 表示从起点出发能否到达位置 i。

初始化 dp[0] = true（起点可达）。

状态转移：若 dp[i] == true，则将 [i+1, i+nums[i]] 范围内所有位置标记为可达。

最终返回 dp[n-1]。

相比贪心，DP 需要额外 O(n) 空间，且内层循环导致最坏 O(n²) 时间，不如贪心高效。

复杂度分析：

时间复杂度：O(n²)，其中 n 为数组长度，最坏情况下内外层各遍历 n 次

空间复杂度：O(n)，需要长度为 n 的布尔数组存储可达状态

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        // dp[i] 表示位置 i 是否可达
        boolean[] dp = new boolean[n];
        dp[0] = true;
        for (int i = 0; i < n; i++) {
            // 只从可达位置出发进行扩展
            if (dp[i]) {
                for (int j = i + 1; j <= i + nums[i] && j < n; j++) {
                    dp[j] = true;
                }
            }
        }
        return dp[n - 1];
    }
}

func canJump(nums []int) bool {
	n := len(nums)
	// dp[i] 表示位置 i 是否可达
	dp := make([]bool, n)
	dp[0] = true
	for i := 0; i < n; i++ {
		// 只从可达位置出发进行扩展
		if dp[i] {
			for j := i + 1; j <= i+nums[i] && j < n; j++ {
				dp[j] = true
			}
		}
	}
	return dp[n-1]
}

相似题目

题目	难度	考察点
45. 跳跃游戏 II	中等	贪心
1306. 跳跃游戏 III	中等	BFS / DFS
1345. 跳跃游戏 IV	困难	BFS、哈希表
1871. 跳跃游戏 VII	中等	前缀和、贪心
134. 加油站	中等	贪心
376. 摆动序列	中等	贪心、动态规划
763. 划分字母区间	中等	贪心

本文作者: HGNULB

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