45. 跳跃游戏 II

LeetCode 45¹ · 中等 · 贪心算法

题

数组 nums 里每个数是在该位置最多能往前跳几步，从下标 0 出发，保证能到最后一个下标，求最少跳几次。

例：nums = [2, 3, 1, 1, 4] → 2（0 → 1 → 4）。

一句话

k 跳能到的位置是一段连续区间；扫到当前区间的右边界 end 时，必须再跳一次，新边界是区间内所有位置能到的最远处 far。

关键技巧

把 BFS 的「层」压成区间。 从 0 出发做 BFS，第 k 层就是恰好 k 跳首次到达的位置。由 55. 跳跃游戏 的结论，可达集合总是前缀，所以每一层是一段连续区间 [start, end]——不用队列，两个指针就能表示一层。

层内扫描求下一层边界。 扫第 k 层时，用 far = max(far, i + nums[i]) 记录下一层的右端；i 走到 end 就「出层」：jumps += 1，end = far。

为什么贪心不亏。 它就是 BFS，BFS 按层扩展天然给出最短步数；「贪心」只体现在不去关心具体跳到层里哪个点——层内任何点都只花 k 跳，谁能跳得最远就让谁定义下一层。

循环只到 n - 2。 站在最后一格不需要再跳；若扫到 n - 1，恰好 i == end 时会多算一跳。

解

class Solution:
    def jump(self, nums: List[int]) -> int:
        jumps = end = far = 0
        for i in range(len(nums) - 1):  # 终点不用再起跳
            far = max(far, i + nums[i])
            if i == end:                # 当前层扫完，必须再跳一次
                jumps += 1
                end = far
        return jumps

时间 \(O(n)\)，空间 \(O(1)\)。

延伸

• 只问能不能到：55. 跳跃游戏，同一个 far，不分层。
• 显式 BFS 的原型：102. 二叉树的层序遍历、994. 腐烂的橘子——按层计数的套路相同，这里只是层恰好连续。
• DP 写法 dp[i] = min(dp[j] + 1) 是 \(O(n^2)\)，能过但没必要。

s = Solution()
assert s.jump([2, 3, 1, 1, 4]) == 2
assert s.jump([2, 3, 0, 1, 4]) == 2
assert s.jump([0]) == 0
assert s.jump([1, 1, 1, 1]) == 3