贪心算法专题(五)：覆盖范围的艺术——「跳跃游戏」

哈喽各位，我是前端小L。

欢迎来到贪心算法专题第五篇！ 想象一下，你站在一个长长的走廊里，地面上标着数字。每个数字代表你在当前位置最多能向前跳几步（你可以跳满，也可以只跳一步）。 你的目标很简单：判断你能否从起点一直跳到终点？

这道题容易陷入的一个误区是：纠结于“我是跳 1 步好，还是跳 2 步好？”。 如果我们去模拟每一种跳法，那这就变成回溯问题了，复杂度会很高。

贪心算法告诉我们：别纠结具体跳几步，只看你最远能覆盖到哪！

力扣 55. 跳跃游戏

https://leetcode.cn/problems/jump-game/

题目分析：

• 输入：非负整数数组nums。

• 规则：nums[i]代表你在位置i的最大跳跃长度。

• 目标：判断是否能到达最后一个下标。

例子 1：[2, 3, 1, 1, 4]

• 在下标 0（数值2）：最远能覆盖到下标 2。

• 我们走到下标 1（数值3）：最远能覆盖到下标1 + 3 = 4。

• 既然能覆盖到 4（即终点），那就返回true。

例子 2：[3, 2, 1, 0, 4]

• 在下标 0（数值3）：最远覆盖到 3。

• 在下标 1（数值2）：最远覆盖到1 + 2 = 3。

• 在下标 2（数值1）：最远覆盖到2 + 1 = 3。

• 在下标 3（数值0）：最远覆盖到3 + 0 = 3。

• 无论如何都跨不过下标 3 这个坎，到不了终点 4。返回false。

核心思维：维护“最大覆盖范围”

我们要把问题转化为：在这个覆盖范围内，我能不能把覆盖范围进一步扩大？

1. Cover: 我们维护一个变量cover，表示当前最远能走到的下标。初始时，我们在起点，cover = 0。

2. 移动：我们在0到cover的范围内遍历每一个位置i。

   • 注意：我们只能在cover范围内移动！如果你当前的位置i已经超过了cover，说明你根本跳不到这儿，游戏结束。

3. 更新：对于遍历到的位置i，我们计算这一跳能达到的最远距离：i + nums[i]。

   • 如果i + nums[i]比当前的cover还要大，我们就更新cover。

4. 判定：一旦cover >= nums.size() - 1（终点下标），说明终点已经被覆盖了，直接返回true。

贪心策略：不管我怎么跳，我每一步都尽可能去更新最大的覆盖范围。只要终点在这个范围内，我就赢了。

算法流程

1. cover = 0。

2. 如果数组只有一个元素，直接返回true。

3. 遍历i从0到nums.size() - 2（其实只需要遍历到cover即可，但为了代码简单，我们用循环控制）：

   • 关键约束：只有当i <= cover时，我们才能站在i上。

   • 贪心更新：cover = max(cover, i + nums[i])。

   • 提前结束：如果cover >= nums.size() - 1，返回true。

4. 循环结束后，如果还没返回true，说明到不了，返回false。

代码实现 (C++)

C++

#include <vector> #include <algorithm> using namespace std; class Solution { public: bool canJump(vector<int>& nums) { int cover = 0; // 当前能覆盖到的最远下标 // 只有一个元素，肯定能到 if (nums.size() == 1) return true; // 注意：i 只能在 cover 范围内移动 // 虽然循环写的是 i <= cover，但 cover 是在动态增长的 for (int i = 0; i <= cover; i++) { // 更新覆盖范围 cover = max(cover, i + nums[i]); // 如果覆盖范围已经包含了终点 if (cover >= nums.size() - 1) { return true; } } // 跑完所有能跑的地方，还是没覆盖到终点 return false; } };

深度复杂度分析

• 时间复杂度：O(N)

  • 我们最多遍历数组一次。

• 空间复杂度：O(1)

  • 只需要一个变量cover。

总结：格局打开

这道题展示了贪心算法的一种**“宏观视角”。 我们没有去纠结微观的“第一步跳几米，第二步跳几米”，而是直接审视“势能”**（覆盖范围）。

• 只要我的势能足够大，能罩住终点，那具体怎么跳，总归是有办法的。

下一题预告：跳跃游戏 II

现在难度升级了！ 如果在上一题的基础上，我保证一定能跳到终点，但我要求你求出最少跳几步能到？

这时候，“最大覆盖范围”这个单一指标就不够用了。我们需要两个指标：“当前这一步最远能到哪”和“下一步最远能到哪”。 这道题是贪心算法中逻辑稍微复杂一点的题目，准备好烧脑了吗？

下期见！