跳跃游戏 II 图解题解

这道题到底在问什么

nums

[2, 3, 1, 1, 4]

输出

2 （0 → 1 → 4）

最优解：一步一步想明白

1. 3设 dp[i] 为跳到 i 的最少次数，每格都回看前面所有能跳到它的格子取最小——两重循环 O(n²)。其实不必逐格记账，一遍贪心就够。
2. 4转折：当前这一跳能覆盖一段范围 [.. curEnd]，就像 BFS 的一层。在这一层里逐格走时，不断用 farthest = max(farthest, i + nums[i]) 记下「下一跳最远能摸到哪」。一旦走到 curEnd（这一层探完了），就必须再跳一次：jumps += 1 并把 curEnd 推到 farthest（进入下一层）。为什么贪心对：同一层里的格子都用一跳可达，下一层的最远边界就是它们能摸到的最远点。
3. 5curEnd=0, farthest=2, jumps=0第一层范围只有 [0,0]。在 0 处算出下一跳最远能到 0+2=2，记下 farthest=2。jumps 仍是 0。
4. 6i==curEnd → jumps=1i 正好等于当前边界 curEnd=0，这一层探完了，必须跳一次：jumps=1，新边界 curEnd 推到 farthest=2。橙色范围扩到 [0,2]，这是第一跳能覆盖的一层。
5. 7farthest = 4在第一跳范围 [0,2] 内走到 1，它能蹦到 1+3=4，刷新 farthest=4。i=1 还没到边界 curEnd=2，先不加跳数，继续探。
6. 8farthest 仍 = 4走到 2，它只能到 2+1=3，没超过现有的 4，farthest 不变。但 i=2 已经撞到 curEnd=2——这一层（第一跳的覆盖范围）探完了。
7. 9i==curEnd → jumps=2i 触到边界 curEnd=2，必须再跳一次：jumps=2，新边界 curEnd 推到 farthest=4。注意这一跳的「最远潜力」是从前面 1 号位探出来的——这正是贪心的价值。
8. 10farthest 仍 = 4走到 3，它能到 3+1=4，没超过现有 farthest=4。i=3 还没到边界 curEnd=4，不加跳数。这也是循环的倒数第二格。
9. 11curEnd 4 ≥ 末尾 4边界 curEnd=4 已经盖住终点。循环只走到倒数第二格（i=3）就停，不会在末尾误加跳数。
10. 12jumps = 2路径 0 → 1 → 4，最少跳跃次数 = 2。全程一遍扫描，没有回头。
11. 15不纠结具体跳到哪一格，只盯「这一层范围里能把下次边界推多远」——这是区间贪心，本质就是隐式的 BFS 分层。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def jump(self, nums):
        jumps = 0
        curEnd = 0        # 当前这一跳能落的最远边界
        farthest = 0      # 这段里探到的下一跳最远
        for i in range(len(nums) - 1):   # 只到 n-2
            farthest = max(farthest, i + nums[i])
            if i == curEnd:              # 走到边界→必须跳一次
                jumps += 1
                curEnd = farthest
        return jumps

class Solution {
public:
    int jump(vector<int>& nums) {
        int jumps = 0, curEnd = 0, farthest = 0;
        for (int i = 0; i + 1 < nums.size(); i++) {
            farthest = max(farthest, i + nums[i]);
            if (i == curEnd) { jumps++; curEnd = farthest; }  // 边界到了，跳
        }
        return jumps;
    }
};

class Solution {
    public int jump(int[] nums) {
        int jumps = 0, curEnd = 0, farthest = 0;
        for (int i = 0; i + 1 < nums.length; i++) {
            farthest = Math.max(farthest, i + nums[i]);
            if (i == curEnd) { jumps++; curEnd = farthest; }  // 边界到了，跳
        }
        return jumps;
    }
}

cnt, curEnd, farthest = 0, 0, 0
for i in range(n - 1):
    farthest = max(farthest, i + maxReach(i))
    if i == curEnd:                  # 到边界，必须推进一层
        cnt += 1; curEnd = farthest
return cnt

复杂度

面试官可能追问