荆州市网站建设_网站建设公司_Banner设计_seo优化

哈喽各位，我是前端小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]。

• 目标：最小跳跃次数。

核心思维：维护当前步数的“边界”

我们需要两个关键变量来记录覆盖范围：

1. curDistance：当前这一步最远能覆盖到的位置。

2. nextDistance：如果再多跳一步，最远能覆盖到的位置。

逻辑推演：我们遍历每一个位置i：

• 在遍历过程中，不断计算并更新nextDistance = max(nextDistance, i + nums[i])。这代表“如果我在当前范围内找一个跳板，它最远能送我去哪”。

• 当i走到了curDistance（也就是走到了当前这一步的边界）：

  • 说明这一步的潜力耗尽了，我们必须进行下一次跳跃了。

  • 此时，steps++。

  • 将curDistance更新为nextDistance（把边界推得更远）。

  • 检查新的curDistance是否覆盖了终点，如果覆盖了，直接结束。

[Image visualization: Current reach boundary vs Next reach boundary]

贪心策略：不用纠结具体跳到哪个格子，我只关心**“在当前这一步的范围内，我能蓄力到的最远下一跳边界在哪里”**。当走到当前边界时，果断切换到下一跳的边界。

算法流程

1. 如果数组长度为 1，直接返回 0（不用跳）。

2. 初始化：

   • curDistance = 0

   • nextDistance = 0

   • steps = 0

3. 遍历i从0到nums.size() - 2：

   • 注意：这里只需要遍历到倒数第二个元素！

   • 原因：如果我们在倒数第二个位置（或之前）更新了边界，且这个边界已经覆盖了终点，那步数就已经加了。遍历最后一个元素没有意义（我们已经在终点了，不需要再起跳）。

4. 在循环中：

   • 更新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）。

下期见！