LeetCode 跳跃游戏 II 最优解法：贪心算法

在刷LeetCode的过程中，跳跃游戏 II（Jump Game II） 是一道经典的贪心算法题目，要求我们以最少的跳跃次数到达数组的最后一个位置。这篇文章将详细讲解如何用贪心思想高效解决这个问题，全程使用Java代码实现，思路清晰且时间复杂度最优。

题目回顾

给定一个长度为 n的非负整数数组 nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个下标。

说明：假设你总是可以到达数组的最后一个位置。

解题思路：贪心算法

核心思想是每一步都选择能跳得最远的位置，从而最小化跳跃次数。我们通过三个关键变量来实现这个思路：

• mx：记录当前位置能够到达的最远位置；
• last：记录上一次跳跃后到达的边界位置（即上一次跳跃的终点）；
• ans：记录跳跃的总次数。

具体执行步骤：

1. 遍历数组的前n-2个位置（因为到达倒数第二个位置时，最后一次跳跃必然能到终点）；
2. 对每个位置i，计算i + nums[i]（当前位置能跳到的最远位置），并更新mx为全局最大值；
3. 当遍历到last（上一次跳跃的边界）时，说明需要进行一次新的跳跃：
   • 将last更新为当前能到达的最远位置mx；
   • 跳跃次数ans加 1；
4. 遍历结束后，ans即为最少跳跃次数。

Java代码实现：

class Solution { public int jump(int[] nums) { // 边界处理：数组长度为1时，无需跳跃 if (nums == null || nums.length <= 1) { return 0; } int n = nums.length; int mx = 0; // 当前能到达的最远位置 int last = 0; // 上一次跳跃的边界位置 int ans = 0; // 跳跃次数 // 遍历到n-2即可，因为到n-1已经是终点，无需再跳 for (int i = 0; i < n - 1; i++) { // 更新当前能到达的最远位置 mx = Math.max(mx, i + nums[i]); // 到达上一次跳跃的边界，需要跳一次 if (i == last) { last = mx; // 新的边界是当前能到达的最远位置 ans++; // 跳跃次数+1 // 提前终止：如果当前最远位置已经能到终点，无需继续遍历 if (mx >= n - 1) { break; } } } return ans; } }

代码解析

1. 边界处理：如果数组长度小于等于 1，直接返回 0（起点就是终点，无需跳跃）；
2. 变量初始化：mx初始为 0（初始能到达的最远位置），last初始为 0（初始跳跃边界是起点），ans初始为 0（初始跳跃次数）；
3. 核心遍历：
   • 遍历范围是[0, n-2]，因为当i = n-1时已经到达终点，无需处理；
   • 每次计算i + nums[i]并更新mx，确保mx始终是当前能到达的最远位置；
   • 当i到达上一次跳跃的边界last时，说明必须跳一次：更新last为新的最远边界mx，并增加跳跃次数；
4. 提前终止优化：如果mx已经能覆盖到数组最后一个位置，直接跳出循环，减少不必要的遍历。

复杂度分析

• 时间复杂度：O(n)，仅需遍历数组一次，每个元素最多被访问一次；
• 空间复杂度：O(1)，仅使用了常数个变量，没有额外的空间开销。

示例验证

以nums = [2,3,1,1,4]为例：

• 初始：mx=0, last=0, ans=0；
• i=0：mx = max(0, 0+2)=2，i==last，更新last=2，ans=1；
• i=1：mx = max(2, 1+3)=4，i≠last；
• i=2：mx = max(4, 2+1)=4，i==last，更新last=4，ans=2；此时mx=4 >= 4（数组最后一个位置），提前终止；
• 最终返回ans=2，符合预期。

总结

1. 本题的核心是贪心策略：每一步都选择能跳得最远的位置，从而最小化跳跃次数；
2. 通过mx记录最远可达位置、last记录跳跃边界，能在一次遍历中完成计算，时间复杂度最优；
3. Java 代码实现中加入了边界处理和提前终止优化，进一步提升了代码的健壮性和效率。