：覆盖范围的艺术——「跳跃游戏」)
哈喽各位，我是前端小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。
核心思维：维护“最大覆盖范围”
我们要把问题转化为：在这个覆盖范围内，我能不能把覆盖范围进一步扩大？
Cover: 我们维护一个变量
cover，表示当前最远能走到的下标。初始时，我们在起点，cover = 0。移动：我们在
0到cover的范围内遍历每一个位置i。注意：我们只能在
cover范围内移动！如果你当前的位置i已经超过了cover，说明你根本跳不到这儿，游戏结束。
更新：对于遍历到的位置
i，我们计算这一跳能达到的最远距离：i + nums[i]。如果
i + nums[i]比当前的cover还要大，我们就更新cover。
判定：一旦
cover >= nums.size() - 1（终点下标），说明终点已经被覆盖了，直接返回true。
贪心策略：不管我怎么跳，我每一步都尽可能去更新最大的覆盖范围。只要终点在这个范围内，我就赢了。
算法流程
cover = 0。如果数组只有一个元素，直接返回
true。遍历
i从0到nums.size() - 2（其实只需要遍历到cover即可，但为了代码简单，我们用循环控制）：关键约束：只有当
i <= cover时，我们才能站在i上。贪心更新：
cover = max(cover, i + nums[i])。提前结束：如果
cover >= nums.size() - 1，返回true。
循环结束后，如果还没返回
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
现在难度升级了！ 如果在上一题的基础上，我保证一定能跳到终点，但我要求你求出最少跳几步能到？
这时候，“最大覆盖范围”这个单一指标就不够用了。我们需要两个指标：“当前这一步最远能到哪”和“下一步最远能到哪”。 这道题是贪心算法中逻辑稍微复杂一点的题目，准备好烧脑了吗？
下期见！
