跳跃游戏 II 图解题解

从下标 0 跳到末尾，最少跳几次

nums[i] 是站在下标 i 时最多能往右跳的步数——写着 3，就是往右 1 步到 3 步随你挑。从下标 0 出发，题目保证一定跳得到最后一格，问最少跳几次。题面例子 nums=[2,3,1,1,4]，答案是 2：先落到下标 1，再一步跳到下标 4。

逐格记最少跳数，为什么会到 O(n²)

按定义硬记的话，给每格标一个『到这里最少跳几次』：下标 0 是 0，之后每到一格，回头看前面所有能一步跳到它的格子，挑里面最小的跳数加一。麻烦在每标一格都要往回扫一遍前面的格子，n 格摞起来是 n×n 级比较，数据一大就掉进 O(n²)，操作量随规模翻平方地涨。

不盯具体落点，只盯这一跳能摸到多远

换成贪心来跳，每一步只做当下最划算的选择、不回头。这里最划算的不是『跳到哪个具体格子』，而是让下一跳的落脚范围尽量往右够。道理在于：当前这一跳能落脚的格子里，不管你停在哪一格，决定后面还要跳几次的，只是它们当中谁能摸到最远的下标。既然落哪都不影响，就把这一跳折成一个数——它能延伸到的最远边界。

于是分层来看：第一跳从下标 0 覆盖的一段是第一层，这层里所有格子能摸到的最远处，就是第二跳的右边界、第二层的尽头。走到一层的尽头，就必须再跳一次进下一层。每层都把边界伸到最远，层数压到最少，跳数就最少。

end、farthest、jumps 各盯一件事

落到代码就三个变量：end 是当前这一跳的右边界，farthest 是边扫边探到的、下一跳能达到的最远处，jumps 是已跳次数。从左往右扫，每到一格 i 就用 i+nums[i] 更新 farthest、对整段区间取最大——区间里靠后的某格可能摸得更远。一旦 i 撞上 end，说明这一跳的落脚区间扫完了，jumps 加一，并把 end 推到 farthest 进入下一层。

[2,3,1,1,4] 上手扫一遍，2 跳怎么来的

三个变量都从 0 起。先看下标 0：farthest 取 max(0,0+2)=2；它正好等于 end=0，跳一次让 jumps=1，end 推到 2。到下标 1：farthest 取 max(2,1+3)=4，可还没到 end=2，只更新不跳。到下标 2：farthest 取 max(4,2+1)=4，这次撞上 end=2，再跳一次 jumps=2，end 推到 4。到下标 3：farthest 取 max(4,3+1)=4，没到 end=4，不跳。下标 4 是终点不进循环，扫到下标 3 就收手，返回 jumps=2。

循环边界和落点，一写偏就得多跳

循环若写到最后一格才停，站上终点还会再判一次 i==end、白多跳一回，写成扫到倒数第二格为止才对。撞到 end 时别急着拿 nums[i] 当落点往前挪，贪心要的是整段区间摸到的最远边界 farthest，具体停哪格不影响后面的跳数。farthest 也不能只看当前这一格的 i+nums[i]，得对整段区间一路取最大，区间里更靠后的某格常常伸得更远，漏了 max 就会少算一跳。这套扫法把数组从左到右过一遍、每格做常数次比较，时间 O(n)；只用三个变量、不开数组，空间 O(1)。

Python

def jump(nums):
    jumps = end = farthest = 0
    for i in range(len(nums) - 1):     # 最后一格不用再起跳
        farthest = max(farthest, i + nums[i])  # 当前区间能摸到的最远
        if i == end:                  # 扫到当前跳的右边界
            jumps += 1                # 必须跳一次
            end = farthest            # 下一跳右边界 = farthest
    return jumps

C++

int jump(vector<int>& nums) {
    int jumps = 0, end = 0, farthest = 0;
    for (int i = 0; i + 1 < (int)nums.size(); ++i) {
        farthest = max(farthest, i + nums[i]);  // 区间内最远
        if (i == end) {            // 到当前跳右边界
            ++jumps;               // 跳一次
            end = farthest;        // 更新下一跳右边界
        }
    }
    return jumps;
}

Java

public int jump(int[] nums) {
    int jumps = 0, end = 0, farthest = 0;
    for (int i = 0; i < nums.length - 1; i++) {
        farthest = Math.max(farthest, i + nums[i]); // 区间内最远
        if (i == end) {            // 到当前跳右边界
            jumps++;               // 跳一次
            end = farthest;        // 更新下一跳右边界
        }
    }
    return jumps;
}