Java版LeetCode热题100之跳跃游戏：贪心算法的完美应用

• 思路：从位置0开始，尝试所有可能的跳跃步数，递归检查是否能到达终点
• 实现：对每个位置i，遍历所有可能的下一步位置[i+1, i+nums[i]]
• 问题：时间复杂度过高，存在大量重复计算

为什么暴力法不够好？

• 最坏情况下时间复杂度为$O(2^n)$（每个位置都有多种选择）
• 对于$n = 10^4$的数据规模，这是完全不可行的
• 即使使用记忆化搜索，空间复杂度也会很高

💡 关键洞察：我们不需要知道具体的跳跃路径，只需要知道最远能到达哪里！

三、答案构思

3.1 核心思想：贪心算法

'维护当前能够到达的最远位置，如果这个位置能够覆盖终点，就返回true'

这个简单而强大的思想让我们避免了复杂的路径搜索：

• 维护一个变量rightmost：记录当前能够到达的最远位置
• 遍历每个位置：如果当前位置可达（i ≤ rightmost），就用它更新最远位置
• 提前终止：一旦最远位置≥终点，立即返回true

3.2 算法步骤

1. 初始化rightmost = 0（起始位置）
2. 遍历数组中的每个位置i：
   • 如果i > rightmost，说明当前位置不可达，后续位置也都不可能到达，返回false
   • 否则，用i + nums[i]更新rightmost
   • 如果rightmost ≥ n-1，说明终点可达，返回true
3. 遍历结束后仍未到达终点，返回false

3.3 为什么贪心策略有效？

• 最优子结构：如果位置x可达，那么[0, x]范围内的所有位置都可达
• 贪心选择性质：在每个可达位置，我们都选择能够跳得最远的策略
• 无后效性：过去的跳跃选择不会影响未来的可达性判断

✅ 贪心算法的核心：通过维护全局最优状态（最远可达位置），避免了枚举所有可能的路径。

四、完整答案（Java实现）

4.1 方法一：贪心算法（推荐）

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;
    }
}

4.2 方法二：优化的贪心算法（更简洁）

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;
    }
}

4.3 方法三：动态规划（仅用于理解，效率较低）

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];
    }
}

✅ 方法二最推荐：代码简洁，逻辑清晰，性能最优。

五、代码分析

5.1 关键变量含义

• rightmost：当前能够到达的最远位置（包含该位置）
  • 初始值为0，表示起始位置
  • 在遍历过程中不断更新为更大的值
• 循环条件：遍历每个位置i，检查是否可达并更新状态

5.2 执行过程示例

示例1：nums = [2,3,1,1,4]

结果：返回true，在i=1时就发现可以到达终点。

示例2：nums = [3,2,1,0,4]

结果：返回false，在i=4时发现当前位置不可达。

5.3 边界情况处理

• 单元素数组：[5] → 已经在终点，返回true
• 全零数组：[0,0,0] → 只有第一个位置可达，返回false（除非长度为1）
• 递增数组：[1,2,3,4,5] → 肯定可达，早期就能返回true
• 递减数组：[5,4,3,2,1] → 肯定可达，因为起始位置就能跳到最后

5.4 代码风格对比

原始版本 vs 优化版本：

// 原始版本（显式break）
if(i <= rightmost){
    // 更新逻辑
}else{
    break;
}

// 优化版本（直接return）
if(i > rightmost){
    return false;
}
// 更新逻辑

优缺点对比：

• 原始版本：逻辑分支更清晰，便于调试
• 优化版本：代码更简洁，减少嵌套层级

📌 建议：在面试中使用优化版本，既简洁又高效。

六、时间复杂度与空间复杂度分析

6.1 贪心算法

• 时间复杂度：$O(n)$
  • 最坏情况下需要遍历整个数组一次
  • 每次操作都是常数时间
  • 最好情况下：如果起始位置就能跳到终点，时间复杂度为$O(1)$
• 空间复杂度：$O(1)$
  • 只使用了常数个额外变量：rightmost, n, i

6.2 动态规划

• 时间复杂度：$O(n^2)$
  • 外层循环：$n$次
  • 内层循环：平均$\frac{n}{2}$次
  • 总操作次数：约$\frac{n^2}{2}$
• 空间复杂度：$O(n)$
  • 需要额外的dp数组存储每个位置的可达性

6.3 性能对比

📊 结论：贪心算法在时间和空间上都是最优的，完美满足题目要求。

七、常见问题解答（FAQ）

Q1：为什么不需要考虑具体的跳跃路径？

答：因为我们只关心是否可达，而不关心如何到达。贪心算法通过维护最远可达位置，确保了如果终点可达，我们一定能检测到。具体的路径信息是冗余的。

Q2：如果数组中有很大的数字（比如10^5），会不会导致数组越界？

答：不会。我们在更新rightmost时，实际上不需要担心越界，因为：如果i + nums[i] >= n-1，我们直接返回true即使rightmost超过n-1，也只是表示可以跳得更远，不影响正确性Java数组访问有边界检查，但我们并没有实际访问nums[rightmost]

Q3：为什么贪心算法在这里有效，而在其他问题中可能无效？

答：贪心算法的有效性取决于问题是否具有贪心选择性质和最优子结构。在跳跃游戏中：贪心选择性质：在每个可达位置，选择能跳得最远的策略不会影响最终结果最优子结构：全局最优解（能否到达终点）可以通过局部最优解（最远可达位置）得到

Q4：如何修改算法来返回最少跳跃次数？

答：这就变成了LeetCode 45题"跳跃游戏 II"。需要使用BFS或贪心的变种：

Q5：如果允许向左跳跃，算法还适用吗？

答：不适用。向左跳跃会引入循环依赖，可能需要使用图论算法（如BFS/DFS）来解决。原问题的关键假设是只能向右跳跃。

八、优化思路

8.1 优化1：提前终止条件

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 - 1
• 理由：如果能到达位置n-2且nums[n-2] >= 1，就能到达终点

8.2 优化2：特殊模式检测

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);
}

• 适用场景：当数组中很少有0时，可以快速返回true
• 实际效果：在特定数据分布下有性能提升，但增加了代码复杂度

8.3 优化3：内存访问优化

// 使用局部变量缓存数组长度
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访问
• 效果：微小的性能提升，但提高了代码可读性

8.4 进阶优化：并行处理（不适用）

重要提醒：跳跃游戏不能并行化！因为每个位置的可达性依赖于前面位置的计算结果，存在严格的顺序依赖。试图并行化会导致错误的结果。

九、数据结构与算法基础知识点回顾

9.1 贪心算法（Greedy Algorithm）

• 定义：在每一步选择中都采取在当前状态下最好或最优的选择
• 特点：
  • 局部最优 → 全局最优
  • 通常效率很高
  • 不适用于所有问题
• 适用条件：
  • 贪心选择性质：局部最优选择能导致全局最优解
  • 最优子结构：问题的最优解包含子问题的最优解
• 本题应用：在每个可达位置，选择能跳得最远的策略

9.2 可达性问题（Reachability Problem）

• 定义：判断从起始状态是否能够到达目标状态
• 常见解法：
  • BFS/DFS：适用于一般图的可达性
  • 动态规划：适用于有重叠子问题的情况
  • 贪心算法：适用于具有特殊性质的问题
• 本题特点：线性结构 + 单向移动 → 贪心算法最优

9.3 时间复杂度分析

• 线性时间$O(n)$：算法效率的黄金标准
• 为什么能达到线性时间：
  • 每个位置最多被访问一次
  • 状态转移是常数时间
  • 提前终止机制进一步优化实际运行时间

9.4 算法正确性证明

数学归纳法证明贪心算法的正确性：

• 基础情况：位置0可达，rightmost = nums[0]，正确
• 归纳假设：前k个位置的可达性判断正确，rightmost记录了正确的最远位置
• 归纳步骤：位置k+1
  • 如果k+1 ≤ rightmost，说明位置k+1可达，用它更新rightmost
  • 如果k+1 > rightmost，说明位置k+1不可达，算法正确返回false
• 结论：算法对所有位置都正确

9.5 问题建模技巧

• 抽象建模：将具体问题抽象为可达性问题
• 状态定义：用rightmost表示当前状态
• 状态转移：rightmost = max(rightmost, i + nums[i])
• 终止条件：rightmost ≥ n-1

十、面试官提问环节（模拟）

Q1：你的算法时间复杂度是O(n)，空间复杂度是O(1)，还有优化空间吗？

答：从渐进复杂度角度看，已经是最优了。因为我们需要检查每个位置至少一次（Ω(n)下界），所以O(n)时间无法改进。空间复杂度O(1)也是最优的。

但在实际工程中，可以考虑：缓存友好性：顺序访问数组，缓存命中率高分支预测：现代CPU对规律性分支有更好的预测向量化：但对于这种依赖性的算法，向量化帮助有限

Q2：如果要找出具体的跳跃路径，怎么办？

答：需要修改算法来记录路径信息：

注意：这会增加空间复杂度到O(n)，时间复杂度仍然是O(n)。

Q3：如果数组长度是10^6，你的算法还能工作吗？

答：完全可以！我们的算法：时间复杂度：O(n) = 10^6次操作，在现代计算机上不到1毫秒空间复杂度：O(1)，只使用几个整数变量内存访问模式：顺序访问，缓存友好

实际上，这个算法可以轻松处理千万级别的数据。

Q4：如何扩展到二维网格的跳跃问题？

答：二维网格的跳跃问题就变成了图的可达性问题：建模：每个格子是一个节点，跳跃关系是边算法：使用BFS或DFS复杂度：时间O(mn)，空间O(mn)优化：如果跳跃规则有特殊性质，可能有更优解法

Q5：这个算法能处理实时数据流吗？

答：不太适合。跳跃游戏是一个离线问题，需要完整的数组信息。如果是实时数据流（逐个接收数组元素），我们需要不同的策略：在线算法：维护当前最远可达位置挑战：无法预知后续元素，可能需要回溯实际应用：通常跳跃游戏是离线处理的

十一、这道算法题在实际开发中的应用

11.1 游戏开发

• 场景：平台跳跃游戏中的关卡设计
• 应用：验证关卡是否可通关
• 实现：将每个平台的跳跃能力编码为数组，使用贪心算法验证

// 伪代码：游戏关卡验证器
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);
    }
}

11.2 网络路由

• 场景：数据包在网络中的转发
• 应用：验证从源节点到目标节点是否存在有效路径
• 类比：每个路由器的跳数限制 = nums[i]，目标是到达最后一个节点

11.3 资源分配

• 场景：云计算中的资源调度
• 应用：验证任务是否能在给定的资源约束下完成
• 建模：每个时间点的可用资源 = nums[i]，目标是完成所有任务

11.4 编译器优化

• 场景：指令调度和寄存器分配
• 应用：验证指令序列是否可以在硬件约束下执行
• 类比：每个指令的执行窗口 = nums[i]，目标是完成整个程序

11.5 机器人路径规划

• 场景：机器人在网格中的移动
• 应用：验证机器人是否能从起点到达终点
• 扩展：结合障碍物检测，形成更复杂的可达性问题

💡 核心价值：任何需要验证在约束条件下是否能达到目标的场景，都可以借鉴跳跃游戏的解题思路。

十二、相关题目推荐

12.1 题目演进路径

1. 基础版（本题）：判断是否可达，贪心算法
2. 最少步数：求最小跳跃次数，贪心/BFS
3. 双向跳跃：可以向左跳，BFS/DFS
4. 值相等跳跃：可以跳到相同值位置，图论+BFS
5. 带约束跳跃：有额外约束条件，动态规划

12.2 学习建议

• 先掌握本题：理解贪心思想在可达性问题中的应用
• 再挑战45题：理解如何在贪心基础上求最优解（最少步数）
• 最后攻克困难题：掌握图论和动态规划在复杂跳跃问题中的应用
• 总结模式：不同约束条件下选择合适的算法

12.3 扩展练习

• LeetCode 279：完全平方数（BFS求最少步数）
• LeetCode 322：零钱兑换（动态规划求最少硬币数）
• LeetCode 127：单词接龙（BFS求最短路径）

🔔 重点：跳跃游戏系列问题展示了从贪心到BFS到动态规划的算法演进，值得系统学习。

十三、总结与延伸

13.1 核心总结

• 问题本质：线性可达性问题
• 最优解法：贪心算法，一次遍历
• 关键思想：维护当前能够到达的最远位置
• 时间复杂度：$O(n)$，空间复杂度：$O(1)$
• 适用场景：任何需要在线性结构中验证可达性的问题

13.2 算法思想延伸

• 从贪心到图论：
  • 贪心：适用于具有特殊性质的线性问题
  • BFS/DFS：适用于一般的图可达性问题
  • 动态规划：适用于有重叠子问题的优化问题
• 在线 vs 离线：
  • 跳跃游戏是典型的离线问题
  • 在线版本需要不同的算法策略

13.3 工程实践启示

1. 问题抽象能力：将具体业务问题抽象为经典的算法模型
2. 算法选择：根据问题特性选择最合适的算法
3. 边界处理：考虑各种边界情况，确保代码鲁棒性
4. 性能意识：理解算法复杂度，选择最优解决方案
5. 代码简洁性：简洁的代码更容易维护和调试

13.4 学习路线建议

跳跃游戏-可达性判断

跳跃游戏II-最少步数

BFS基础应用

跳跃游戏III-双向跳跃

图论算法

跳跃游戏IV/V-复杂约束

动态规划高级应用

13.5 代码模板记忆

// 跳跃游戏模板
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;
}

// 通用思想：维护全局最优状态，避免枚举所有可能性

🌟 最后寄语：跳跃游戏这道题完美展示了贪心算法的魅力——用最简单的逻辑解决了看似复杂的问题。掌握这道题不仅能够应对面试，更能培养你对算法本质的理解：有时候，最好的策略就是每次都选择能走得最远的那一步。记住，优秀的程序员不仅要会写代码，更要会思考问题的本质。继续前行，算法之路越走越宽广！