跳到主要内容

LeetCode 45. 跳跃游戏 II

本节目标

将连续可达位置看成一层，在层边界耗尽时增加一次跳跃。

这是单序列扫描与边界中“可达性”到“最少次数”的升级。题目保证终点可达，因此可以把一次跳跃能到达的连续区间看作 BFS 的一层。

题意与约束​

从下标 0 出发，每次最多跳 nums[i] 步，求到达最后一个下标的最少跳跃次数。

直接思路与瓶颈​

逐个落点 BFS 可以求最短路，但每个位置会枚举一段后缀，最坏接近 O(n^2)。相同跳数到达的多个位置可合并成一个连续边界。

贪心模型与算法推导​

boundary 是当前跳数能覆盖的最远位置，farthest 是扫描本层位置后下一跳能覆盖的最远位置。扫描到 boundary 时，本层选择已全部比较，必须增加一次跳跃并把 boundary=farthest。最后一个下标不必继续扩展。

正确性依据​

在扫描当前层 [previousBoundary,boundary] 时，所有这些位置都恰好可用当前跳数到达。任何再少一跳的路径不可能越过旧边界；farthest 收集该层全部位置的下一跳最大覆盖范围，所以进入下一层后仍保留所有最优选择。每层只加一次跳，首次覆盖终点的层数最小。

样例执行过程​

[2,3,1,1,4]：初始层只含 0，其下一层边界为 2，跳数变 1；扫描 1,2 时最大可达为 4，到 i=2 进入第二层，跳数变 2，已覆盖终点。[0] 不进入循环，直接返回 0。

代码实现​

C++17
#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
    int jump(vector<int> nums) {
        int jumps = 0;
        int boundary = 0;
        int farthest = 0;
        for (int index = 0; index + 1 < static_cast<int>(nums.size()); ++index) {
            farthest = max(farthest, index + nums[index]);
            if (index == boundary) {
                ++jumps;
                boundary = farthest;
            }
        }
        return jumps;
    }
};

复杂度分析​

每个位置至多扫描一次，时间 O(n)，额外空间 O(1)。

边界与易错点​

  • 在更新 farthest 后判断是否抵达层边界。
  • 循环只到倒数第二个位置，终点无需再触发一次跳跃。
  • 本题保证可达；若不保证，应先处理无法越过当前边界的情况。

模式迁移​

当一次操作能覆盖一个连续区间时，常可用“当前层边界 + 下一层最远边界”代替显式 BFS，例如最少区间覆盖和最少视频拼接。