跳跃游戏 II | 秋招知识库

题目链接 · 灵神原题解（署名来源）

⚠注意：不是在无路可走的那个位置造桥，而是当发现无路可走的时候，时光倒流到能跳到最远点的那个位置造桥。换句话说，在无路可走之前，我们只是在默默地收集信息。当发现无路可走的时候，才从收集到的信息中，选择最远点造桥。所建造的这座桥的左端点（起跳位置）可能在我们当前走的这座桥的中间。

也可以理解成，当发现无路可走的时候，往回跳，选择合适的位置造桥。我们可以在最终算账的时候，把往回跳的情况擦掉，只保留往右跳，也能到达终点。所以往回跳不计入跳跃次数。

答疑

问：为什么这个贪心策略是对的？

答：其实这个做法是对暴力的优化。题目让我们计算到达 $n - 1$ 的最小跳跃次数，暴力的做法是，用暴力搜索（或者 BFS）算出跳一次最远可以到哪，跳两次最远可以到哪，跳三次最远可以到哪……跳到 $n - 1$ 的最小跳跃次数就是答案。设跳 $k$ 次最远可以到达 $curEnd$ ，那么下标在 $[0, curEnd]$ 中的最大的 $i + nums [i]$ ，就是跳 $k + 1$ 次最远可以到达的位置 $nextEnd$ 。当我们遍历到 $i = curEnd$ 时，通过计算遍历过的 $i + nums [i]$ 的最大值，可以算出再跳一步最远能到哪里。这本质是一个递推式（ $k \to k + 1$ ），根据这个递推式，就能从跳 $k = 0$ 步开始（此时最远到达 $0$ ），依次递推算出跳 $k = 1, 2, 3, \dots$ 步后的最远位置。

问：为什么代码只遍历到 $n - 2$ ？

答：这题 $n - 1$ 是终点， $nums [n - 1]$ 这个数没有任何意义，完全可以把这个数删了，在长为 $n - 1$ 的数组上跑这个算法。或者说，遍历到 $nums [n - 2]$ 时，要么已经可以到达终点，要么需要造最后一座桥。 $n - 1$ 已经是终点了，不需要造桥。

问：如果题目没有保证一定能到达 $n - 1$ ，代码要怎么改？

答：见 1326. 灌溉花园的最少水龙头数目，我的题解。

Python 解法1C++ 解法1

python

class Solution:
    def jump(self, nums: List[int]) -> int:
        ans = 0
        cur_end = 0  # 已建造的桥的右端点
        next_end = 0  # 下一座桥的右端点的最大值
        for i in range(len(nums) - 1):
            # 遍历的过程中，记录下一座桥的最远点
            next_end = max(next_end, i + nums[i])
            if i == cur_end:  # 无路可走，必须建桥
                cur_end = next_end  # 建桥后，最远可以到达 next_end
                ans += 1
        return ans

cpp

// C++ 版待补充

C++ 解法2

cpp

class Solution {
public:
    int jump(vector<int>& nums) {
        int ans = 0;
        int cur_end = 0; // 已建造的桥的右端点
        int next_end = 0; // 下一座桥的右端点的最大值
        for (int i = 0; i + 1 < nums.size(); i++) {
            // 遍历的过程中，记录下一座桥的最远点
            next_end = max(next_end, i + nums[i]);
            if (i == cur_end) { // 无路可走，必须建桥
                cur_end = next_end; // 建桥后，最远可以到达 next_end
                ans++;
            }
        }
        return ans;
    }
};

复杂度分析

时间复杂度： $O (n)$ 。其中 $n$ 是 $nums$ 的长度。
空间复杂度： $O (1)$ 。

思考题

如果要输出具体的跳跃方案（每一步跳到哪个位置），怎么做？

欢迎在评论区分享你的思路/代码。

更多相似题目，见下面贪心题单中的「区间贪心」。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

答疑 ​

复杂度分析 ​

思考题 ​

分类题单 ​

答疑

复杂度分析

思考题

分类题单