详细解析了LeetCode第55题跳跃游戏的解法，重点介绍了贪心算法的应用。通过对问题本质的分析，提出了一种高效的解决方案，并提供了完整的Java代码实现。同时讨论了算法的时间和空间复杂度，以及常见的面试问题和实际应用场景。
本文将全面深入剖析 LeetCode 热题第55题《跳跃游戏》，从题目理解、暴力解法、贪心优化、动态规划思路、代码实现、复杂度分析、面试技巧到实际应用场景，层层递进，帮助你彻底掌握这一经典算法问题。
给你一个非负整数数组 nums ，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 。
false示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
这是一个典型的可达性问题，核心要求是：
n-1（最后一个下标）[i+1, i+nums[i]]中的任意位置形式化表达：给定数组nums，是否存在一系列位置p_0=0, p_1, p_2, ..., p_k=n-1，使得对于每个j，都有p_{j+1} ≤ p_j + nums[p_j]。
nums[i] ≥ 0，意味着不会出现"负向跳跃"nums[i]步中的任意步数true[i+1, i+nums[i]]为什么暴力法不够好？
💡 关键洞察：我们不需要知道具体的跳跃路径，只需要知道最远能到达哪里！
'维护当前能够到达的最远位置，如果这个位置能够覆盖终点，就返回true'
这个简单而强大的思想让我们避免了复杂的路径搜索：
rightmost：记录当前能够到达的最远位置i ≤ rightmost），就用它更新最远位置truerightmost = 0（起始位置）i：
i > rightmost，说明当前位置不可达，后续位置也都不可能到达，返回falsei + nums[i]更新rightmostrightmost ≥ n-1，说明终点可达，返回truefalse[0, x]范围内的所有位置都可达✅ 贪心算法的核心：通过维护全局最优状态（最远可达位置），避免了枚举所有可能的路径。
public class Solution {
public boolean canJump(int[] nums) {
int n = nums.length;
// 特殊情况：只有一个元素，已经在终点
if (n == 1) {
return true;
}
int rightmost = 0; // 当前能够到达的最远位置
for (int i = 0; i < n; i++) {
// 如果当前位置可达
if (i <= rightmost) {
// 更新最远可达位置
rightmost = Math.max(rightmost, i + nums[i]);
// 如果已经能够到达或超过终点
if (rightmost >= n - 1) {
return true;
}
} else {
// 当前位置不可达，后续位置也不可能到达
break;
}
}
return false;
}
}
public class Solution {
public boolean canJump(int[] nums) {
int rightmost = 0;
int n = nums.length;
for (int i = 0; i < n; i++) {
if (i > rightmost) {
return false;
}
rightmost = Math.max(rightmost, i + nums[i]);
if (rightmost >= n - 1) {
return true;
}
}
return false;
}
}
public class Solution {
public boolean canJump(int[] nums) {
int n = nums.length;
boolean[] dp = new boolean[n];
dp[0] = true; // 起始位置可达
for (int i = 0; i < n; i++) {
if (!dp[i]) continue; // 当前位置不可达，跳过
// 从位置i可以到达的所有位置
int maxJump = Math.min(i + nums[i], n - 1);
for (int j = i + 1; j <= maxJump; j++) {
dp[j] = true;
}
// 如果终点已可达，提前返回
if (dp[n - 1]) {
return true;
}
}
return dp[n - 1];
}
}
✅ 方法二最推荐：代码简洁，逻辑清晰，性能最优。
rightmost：当前能够到达的最远位置（包含该位置）
i，检查是否可达并更新状态nums = [2,3,1,1,4]| i | nums[i] | i <= rightmost? | rightmost (更新后) | rightmost >= 4? |
|---|---|---|---|---|
| 0 | 2 | true (0<=0) | max(0, 0+2)=2 | false |
| 1 | 3 | true (1<=2) | max(2, 1+3)=4 | true |
结果：返回true，在i=1时就发现可以到达终点。
nums = [3,2,1,0,4]| i | nums[i] | i <= rightmost? | rightmost (更新后) | rightmost >= 4? |
|---|---|---|---|---|
| 0 | 3 | true (0<=0) | max(0, 0+3)=3 | false |
| 1 | 2 | true (1<=3) | max(3, 1+2)=3 | false |
| 2 | 1 | true (2<=3) | max(3, 2+1)=3 | false |
| 3 | 0 | true (3<=3) | max(3, 3+0)=3 | false |
| 4 | 4 | false (4>3) | - | - |
结果：返回false，在i=4时发现当前位置不可达。
[5] → 已经在终点，返回true[0,0,0] → 只有第一个位置可达，返回false（除非长度为1）[1,2,3,4,5] → 肯定可达，早期就能返回true[5,4,3,2,1] → 肯定可达，因为起始位置就能跳到最后原始版本 vs 优化版本：
// 原始版本（显式break）
if(i <= rightmost){
// 更新逻辑
}else{
break;
}
// 优化版本（直接return）
if(i > rightmost){
return false;
}
// 更新逻辑
优缺点对比：
📌 建议：在面试中使用优化版本，既简洁又高效。
rightmost, n, idp数组存储每个位置的可达性| 方法 | 时间复杂度 | 空间复杂度 | 实际运行时间（n=10^4） |
|---|---|---|---|
| 贪心算法 | $O(n)$ | $O(1)$ | ~0.1毫秒 |
| 动态规划 | $O(n^2)$ | $O(n)$ | ~50毫秒 |
| 递归回溯 | $O(2^n)$ | $O(n)$ | 超时 |
📊 结论：贪心算法在时间和空间上都是最优的，完美满足题目要求。
答：因为我们只关心是否可达，而不关心如何到达。贪心算法通过维护最远可达位置，确保了如果终点可达，我们一定能检测到。具体的路径信息是冗余的。
答：不会。我们在更新
rightmost时，实际上不需要担心越界，因为：如果i + nums[i] >= n-1，我们直接返回true即使rightmost超过n-1，也只是表示可以跳得更远，不影响正确性Java数组访问有边界检查，但我们并没有实际访问nums[rightmost]
答：贪心算法的有效性取决于问题是否具有贪心选择性质和最优子结构。在跳跃游戏中：贪心选择性质：在每个可达位置，选择能跳得最远的策略不会影响最终结果最优子结构：全局最优解（能否到达终点）可以通过局部最优解（最远可达位置）得到
答：这就变成了LeetCode 45题"跳跃游戏 II"。需要使用BFS或贪心的变种：
答：不适用。向左跳跃会引入循环依赖，可能需要使用图论算法（如BFS/DFS）来解决。原问题的关键假设是只能向右跳跃。
public boolean canJump(int[] nums) {
if (nums.length == 1) return true;
int rightmost = 0;
// 只需要遍历到 n-2，因为到达 n-1 就成功了
for (int i = 0; i < nums.length - 1; i++) {
if (i > rightmost) {
return false;
}
rightmost = Math.max(rightmost, i + nums[i]);
// 提前检查是否能到达终点
if (rightmost >= nums.length - 1) {
return true;
}
}
return false;
}
i < nums.length - 1n-2且nums[n-2] >= 1，就能到达终点public boolean canJump(int[] nums) {
// 快速检测：如果数组中没有0，肯定可以到达
boolean hasZero = false;
for (int num : nums) {
if (num == 0) {
hasZero = true;
break;
}
}
if (!hasZero) return true;
// 如果只有最后一个元素是0，也可以到达
if (nums.length > 1 && nums[nums.length - 1] == 0) {
// 检查前面是否能跳过最后一个0
// ... 继续使用贪心算法
}
// 使用标准贪心算法
return standardCanJump(nums);
}
true// 使用局部变量缓存数组长度
public boolean canJump(int[] nums) {
int n = nums.length;
int rightmost = 0;
for (int i = 0; i < n; i++) {
if (i > rightmost) return false;
rightmost = Math.max(rightmost, i + nums[i]);
if (rightmost >= n - 1) return true;
}
return false;
}
nums.length访问重要提醒：跳跃游戏不能并行化！因为每个位置的可达性依赖于前面位置的计算结果，存在严格的顺序依赖。试图并行化会导致错误的结果。
数学归纳法证明贪心算法的正确性：
rightmost = nums[0]，正确rightmost记录了正确的最远位置k+1 ≤ rightmost，说明位置k+1可达，用它更新rightmostk+1 > rightmost，说明位置k+1不可达，算法正确返回falserightmost表示当前状态rightmost = max(rightmost, i + nums[i])rightmost ≥ n-1答：从渐进复杂度角度看，已经是最优了。因为我们需要检查每个位置至少一次（Ω(n)下界），所以O(n)时间无法改进。空间复杂度O(1)也是最优的。
但在实际工程中，可以考虑：缓存友好性：顺序访问数组，缓存命中率高分支预测：现代CPU对规律性分支有更好的预测向量化：但对于这种依赖性的算法，向量化帮助有限
答：需要修改算法来记录路径信息：
注意：这会增加空间复杂度到O(n)，时间复杂度仍然是O(n)。
答：完全可以！我们的算法：时间复杂度：O(n) = 10^6次操作，在现代计算机上不到1毫秒空间复杂度：O(1)，只使用几个整数变量内存访问模式：顺序访问，缓存友好
实际上，这个算法可以轻松处理千万级别的数据。
答：二维网格的跳跃问题就变成了图的可达性问题：建模：每个格子是一个节点，跳跃关系是边算法：使用BFS或DFS复杂度：时间O(mn)，空间O(mn)优化：如果跳跃规则有特殊性质，可能有更优解法
答：不太适合。跳跃游戏是一个离线问题，需要完整的数组信息。如果是实时数据流（逐个接收数组元素），我们需要不同的策略：在线算法：维护当前最远可达位置挑战：无法预知后续元素，可能需要回溯实际应用：通常跳跃游戏是离线处理的
// 伪代码：游戏关卡验证器
public class LevelValidator {
public boolean isLevelCompletable(int[] jumpCapabilities) {
return canJump(jumpCapabilities);
}
// 可以扩展为更复杂的验证逻辑
public ValidationResult validateLevel(int[] jumpCapabilities) {
boolean completable = canJump(jumpCapabilities);
int minJumps = calculateMinJumps(jumpCapabilities);
return new ValidationResult(completable, minJumps);
}
}
nums[i]，目标是到达最后一个节点nums[i]，目标是完成所有任务nums[i]，目标是完成整个程序💡 核心价值：任何需要验证在约束条件下是否能达到目标的场景，都可以借鉴跳跃游戏的解题思路。
| 题号 | 题目 | 难度 | 关联点 |
|---|---|---|---|
| [55] | 跳跃游戏 | 中等 | 本题 |
| [45] | 跳跃游戏 II | 中等 | 求最少跳跃次数 |
| [1306] | 跳跃游戏 III | 中等 | 可以向左或向右跳 |
| [1345] | 跳跃游戏 IV | 困难 | 可以跳到相同值的位置 |
| [1340] | 跳跃游戏 V | 困难 | 有高度限制的跳跃 |
🔔 重点：跳跃游戏系列问题展示了从贪心到BFS到动态规划的算法演进，值得系统学习。
跳跃游戏-可达性判断
跳跃游戏II-最少步数
BFS基础应用
跳跃游戏III-双向跳跃
图论算法
跳跃游戏IV/V-复杂约束
动态规划高级应用
// 跳跃游戏模板
public boolean canJump(int[] nums) {
int rightmost = 0;
int n = nums.length;
for (int i = 0; i < n; i++) {
if (i > rightmost) {
return false;
}
rightmost = Math.max(rightmost, i + nums[i]);
if (rightmost >= n - 1) {
return true;
}
}
return false;
}
// 通用思想：维护全局最优状态，避免枚举所有可能性
🌟 最后寄语：跳跃游戏这道题完美展示了贪心算法的魅力——用最简单的逻辑解决了看似复杂的问题。掌握这道题不仅能够应对面试，更能培养你对算法本质的理解：有时候，最好的策略就是每次都选择能走得最远的那一步。记住，优秀的程序员不仅要会写代码，更要会思考问题的本质。继续前行，算法之路越走越宽广！
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online