企业官网建设流程全解析

class Solution { public: int jump(vector<int>& nums) { int step = 0; // 跳跃次数 int start = 0, end = 0; // 当前这一跳能够覆盖的范围 // 还没有到达最后一个位置 while (end < nums.size() - 1) { int far = 0; // 下一跳最远能到的位置 // 在当前范围内，寻找最远的位置 for (int i = start; i <= end; i++) { far = max(far, i + nums[i]); } // 当前这一跳结束，更新下一跳的范围 start = end; end = far; step++; // 跳了一次 } return step; } };

详细总结

1. 这道题到底在求什么？

给一个数组：

[2, 3, 1, 1, 4]

nums[i]表示：

站在下标i，最多可以向右跳nums[i]步。

和上一道canJump不一样：

• Jump Game I：能不能到终点？→true / false

• Jump Game II：最少需要跳几次？→ 返回step

例如：

0 → 1 → 4

只需要：

2 次

所以答案是2。

2.start和end是最重要的

int start = 0, end = 0;

它们表示：

当前这一轮，我们能够考虑的范围。

例如：

[start, end] = [0, 2]

就表示：

当前位置： 0 1 2 └───────┘ 当前这一跳可以考虑的范围

我们现在不需要马上决定从哪个位置跳。

而是：

把[0,2]里面的所有位置都看一遍，找出下一次跳跃最远能够到哪里。

3.far是干什么的？

int far = 0;

far表示：

在当前范围内，找到的最远位置。

然后：

for (int i = start; i <= end; i++) { far = max(far, i + nums[i]); }

就是不断尝试：

从 i 位置出发： 最远 = i + nums[i]

然后取其中最大的。

例如：

nums = [2, 3, 1, 1, 4]

当前范围：

[0, 2]

那么：

i = 0： 0 + nums[0] = 0 + 2 = 2 i = 1： 1 + nums[1] = 1 + 3 = 4 i = 2： 2 + nums[2] = 2 + 1 = 3

所以：

far = 4

意思是：

在当前这一跳能够到达的范围里，最好的选择可以让下一跳到达 4。

4. 为什么找到far后才step++？

这是这道题最关键的地方。

我们不是：

走一步 step++ 再走一步 step++

而是把一整层能够到达的位置看成一次跳跃。

例如：

nums = [2,3,1,1,4]

第一次：

[0] ↓ 最多可以到 [0,1,2]

所以第一跳的范围是：

[0,2]

然后我们在[0,2]里面寻找下一跳最远能到哪里：

0 → 2 1 → 4 2 → 3

发现最远是：

4

所以第二跳可以到：

4

整个过程：

第1跳： 0 → [0,1,2] 第2跳： [0,1,2] → 4

所以：

step = 2

5.start = end; end = far是什么意思？

start = end; end = far;

可以理解成：

当前范围处理完了，把范围推进到下一层。

比如第一次：

start = 0 end = 0

处理之后发现：

far = 2

更新：

start = 0 end = 2

现在范围变成：

[0,2]

下一轮就在这个范围里继续寻找。

然后发现：

far = 4

再次更新：

start = 2 end = 4

此时：

end == 最后一个位置

结束。

6. 为什么while是这个条件？

while (end < nums.size() - 1)

意思是：

只要当前最远范围还没有覆盖最后一个位置，就继续寻找下一跳。

假设：

nums.size() = 5

最后一个下标就是：

4

所以：

end < 4

如果：

end = 2

说明还没到终点：

0 1 2 3 4 ↑ end

继续。

如果：

end = 4

说明：

0 1 2 3 4 ↑ end

已经覆盖终点了，直接结束。

最后把整个算法串起来

你可以把它想成一层一层地扩展范围：

初始： [0] ↓ 找下一层最远位置 ↓ [0,1,2] ↓ 再找下一层最远位置 ↓ [0,1,2,3,4] ↓ 到终点

对应代码就是：

while (end < nums.size() - 1) { // ① 在当前范围找最远位置 for (int i = start; i <= end; i++) { far = max(far, i + nums[i]); } // ② 跳一次 step++; // ③ 把范围扩展到 far start = end; end = far; }

三个变量一定要分清

最重要的是：

end是“这一跳目前能覆盖到哪里”，far是“在这一跳的范围里寻找后，下一跳最远能覆盖到哪里”。

一句话记忆

当前范围[start,end]内，寻找最远的far；找到后跳一次，并把end更新成far，不断扩大覆盖范围，直到覆盖终点。

这其实就是一个很典型的贪心思想：

每次不急着决定具体从哪个位置跳，而是在当前能够到达的所有位置中，选择能让下一次覆盖范围最大的方案。