：步步为营的极速狂飙——「跳跃游戏 II」)
哈喽各位，我是前端小L。
欢迎来到贪心算法专题第六篇！ 这道题是跳跃游戏的进阶版。想象一下，你还是要从起点跳到终点，但这次我们要比拼速度（步数）。 关键在于：什么时候进行“下一次跳跃”？
比如[2, 3, 1, 1, 4]。
起点是
2，覆盖范围是下标1~2。我们是跳到下标
1（数值3）好呢，还是跳到下标2（数值1）好呢？如果跳到
1，下一跳最远能到1+3=4。如果跳到
2，下一跳最远能到2+1=3。
贪心策略：显然应该选下标
1作为中间跳板，因为它能带我们去更远的地方！
力扣 45. 跳跃游戏 II
https://leetcode.cn/problems/jump-game-ii/
题目分析：
输入：非负整数数组
nums。保证：可以到达
nums[n-1]。目标：最小跳跃次数。
核心思维：维护当前步数的“边界”
我们需要两个关键变量来记录覆盖范围：
curDistance：当前这一步最远能覆盖到的位置。nextDistance：如果再多跳一步，最远能覆盖到的位置。
逻辑推演：我们遍历每一个位置i：
在遍历过程中，不断计算并更新
nextDistance = max(nextDistance, i + nums[i])。这代表“如果我在当前范围内找一个跳板，它最远能送我去哪”。当
i走到了curDistance（也就是走到了当前这一步的边界）：说明这一步的潜力耗尽了，我们必须进行下一次跳跃了。
此时，
steps++。将
curDistance更新为nextDistance（把边界推得更远）。检查新的
curDistance是否覆盖了终点，如果覆盖了，直接结束。
[Image visualization: Current reach boundary vs Next reach boundary]
贪心策略：不用纠结具体跳到哪个格子，我只关心**“在当前这一步的范围内，我能蓄力到的最远下一跳边界在哪里”**。当走到当前边界时，果断切换到下一跳的边界。
算法流程
如果数组长度为 1，直接返回 0（不用跳）。
初始化：
curDistance = 0nextDistance = 0steps = 0
遍历
i从0到nums.size() - 2：注意：这里只需要遍历到倒数第二个元素！
原因：如果我们在倒数第二个位置（或之前）更新了边界，且这个边界已经覆盖了终点，那步数就已经加了。遍历最后一个元素没有意义（我们已经在终点了，不需要再起跳）。
在循环中：
更新
nextDistance = max(nextDistance, i + nums[i])。如果
i == curDistance：需要走下一步了：
steps++。更新边界：
curDistance = nextDistance。剪枝：如果
curDistance >= nums.size() - 1，直接break（虽然题目保证能到，但加上这个判断逻辑更严谨）。
代码实现 (C++)
C++
#include <vector> #include <algorithm> using namespace std; class Solution { public: int jump(vector<int>& nums) { if (nums.size() == 1) return 0; int curDistance = 0; // 当前覆盖的最远距离下标 int nextDistance = 0; // 下一步覆盖的最远距离下标 int steps = 0; // 记录走的最大步数 // 关键点：只遍历到 nums.size() - 2 // 因为如果走到倒数第二个还没结束，意味着一定需要再跳一步才能到终点 // 如果遍历到 nums.size() - 1，可能会多增加一次不必要的步数 for (int i = 0; i < nums.size() - 1; i++) { // 贪心：在当前覆盖范围内，寻找能跳得最远的下一次位置 nextDistance = max(nextDistance, i + nums[i]); // 如果走到了当前步数的边界 if (i == curDistance) { steps++; // 必须再跳一步 curDistance = nextDistance; // 更新边界 // 如果新的边界已经覆盖了终点，提前结束 if (curDistance >= nums.size() - 1) { break; } } } return steps; } };深度辨析：为什么循环只到size - 2？
这是一个容易出错的边界条件。 假设nums = [2, 1]。
i = 0，curDistance初始为 0。i == curDistance，触发更新：steps变成 1。curDistance变成0+2=2(覆盖了终点)。循环结束。返回 1。正确。
假如循环写成i < nums.size()：
i会走到 1。此时curDistance是 2。虽然逻辑上
i != curDistance不会触发steps++，但如果之前的curDistance刚好卡在size-1上，走到最后一个元素时再次触发更新，就会多算一步。核心逻辑：我们在当前点
i是为了起跳。如果你已经站在终点了，就不需要再起跳了。
深度复杂度分析
时间复杂度：O(N)
只需要遍历一次数组。
空间复杂度：O(1)
只需要存储距离和步数。
总结：边界的艺术
这道题展示了贪心算法中**“动态规划式”的思维（虽然没用 DP 数组）。 我们把跳跃过程看作是一层一层的波纹**：
第 1 步能到的范围是 A。
第 2 步能到的范围是 B (由 A 中的点跳出来的)。
我们只需要记录波纹的边缘，每碰到一次边缘，步数就 +1。
下一题预告：如果数组中有负数怎么办？ 题目要求：K 次取反后最大化数组和。 你可以选择任意一个元素取反（乘 -1），这个操作必须执行 K 次。 贪心策略很有趣：先把绝对值最大的负数变成正数；如果负数都变完了 K 还没用完，那就对着最小的非负数反复取反（消耗 K）。
下期见！
：负负得正的极致——「K 次取反后最大化数组和」)
