45. 跳跃游戏 II (Medium)
专题归类： 11-贪心 LeetCode 链接： https://leetcode.cn/problems/jump-game-ii/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给定一个长度为 n 的非负整数数组 nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个下标。假设你总是可以到达数组的最后一个位置。
返回最少的跳跃次数。
示例 1：
输入：nums = [2,3,1,1,4]
输出：2
解释：跳到最后一个下标的最小跳跃次数是 2。
从下标 0 跳到下标 1（跳 1 步），然后从下标 1 跳 3 步到达最后一个下标。
示例 2：
输入：nums = [2,3,0,1,4]
输出：2
题目详细分析
数据范围： 1 <= nums.length <= 10^4，0 <= nums[i] <= 10^5
核心约束：
- 题目保证一定可以到达最后一个位置（与前一题 “55. 跳跃游戏” 不同）
- 每个位置可以跳
[1, nums[i]]步之间的任意长度 - 目标是最少步数，而非”能否到达”
关键洞察：
- 这是一个最少步数问题，等价于 BFS 求最短路径：每条边从位置 i 指向
[i+1, i+nums[i]]的所有位置 - 但 BFS 需要显式建图或
O(n^2)遍历，对于n=10^4可行但不优 - 贪心思想：在当前步数能到达的范围内，选择能跳得最远的那一个位置作为下一步的起点
- 核心是区间分层的思想——第 k 步能到达的范围是一个连续区间，BFS 的每一层就是一步能到达的区间
小白版直白理解
就像玩跳格子游戏，你站在起点，每个格子上写着”从这里最远能跳几格”。你想用最少的跳跃次数到终点。
策略很简单：在当前这一步能跳到的范围内，选一个能让你下一步跳得最远的位置。 就像你要过一条河，先看看脚底下这块区域（当前步数可达范围），从这些石头里选一块能让你下一次跳得最远的那块。
具体点：你的第一步能跳的范围是 [1, nums[0]]，在这个范围内，你要找到哪个位置能让你再跳得更远（即 i + nums[i] 最大），选它作为下一步的起点。两步能到的范围就变成了 [原范围, 最远位置]，以此类推。
解题思路
思路一：贪心——区间分层 BFS（推荐）
思路讲解： 维护三个变量：
end：当前步数能到达的最远边界（当前 BFS 层的右边界）max_reach：遍历过程中能到达的最远位置（下一层能到的最远位置）steps：已使用的步数
遍历数组（不访问最后一个元素，因为不需要从最后一个位置起跳）：
- 更新
max_reach = max(max_reach, i + nums[i]) - 如果
i == end，说明当前层遍历完毕，步数 +1，将end更新为max_reach（进入下一层）
每步操作相当于：在当前层内探索，找到下一层能到达的最远距离，当走完当前层时，步数增加，进入下一层。
def jump(nums):
n = len(nums)
if n == 1:
return 0
end = 0 # 当前步数能到达的最远边界
max_reach = 0 # 遍历过程中能到达的最远位置
steps = 0
# 不需要遍历最后一个元素（n-1），因为到达 n-1 时已经完成
for i in range(n - 1):
max_reach = max(max_reach, i + nums[i])
# 到达当前步数的边界，步数 +1，更新边界
if i == end:
steps += 1
end = max_reach
return steps时间复杂度： O(n) | 空间复杂度： O(1)
思路二：逆向贪心（从后往前）
思路讲解： 从终点出发，每次找能跳到当前位置的最左边的位置（贪心地让每一步尽量靠左）。虽然直观，但最坏时间复杂度可能退化到 O(n^2)。
def jump(nums):
n = len(nums)
position = n - 1
steps = 0
while position > 0:
for i in range(position):
if i + nums[i] >= position:
position = i
steps += 1
break
return steps时间复杂度： O(n^2)（最坏） | 空间复杂度： O(1)
思路三：动态规划
思路讲解： dp[i] 表示到达位置 i 的最小步数。对于每个可达位置 j，更新 dp[j] = min(dp[j], dp[i] + 1)。复杂度较高，仅作思路参考。
def jump(nums):
n = len(nums)
dp = [float('inf')] * n
dp[0] = 0
for i in range(n):
for j in range(1, nums[i] + 1):
if i + j < n:
dp[i + j] = min(dp[i + j], dp[i] + 1)
return dp[n - 1]时间复杂度： O(n^2)（最坏） | 空间复杂度： O(n)
易错点
- 数组长度为 1：已经在终点，不需要跳跃，返回 0。正向贪心的循环中由于
range(n - 1)在n=1时为空，但在代码开头直接处理更安全 - 不需要遍历最后一个元素：
range(n - 1)而非range(n)，因为到达n-1时已经完成任务，不需要再从最后一个位置起跳 end的更新时机：必须在i == end时更新步数，然后将end设为max_reach。如果提前更新步数会导致计数错误max_reach可能小于end的情况：如果某次边界内所有位置的跳跃能力都很差，max_reach可能等于end（即无法前进），但题目保证可达所以不会死循环- 边界条件
end = 0：第一步时i == 0 == end，会触发步数 +1，这是正确的——第一次起跳就计为一步
框架提炼
贪心模板：最少跳跃 / BFS 分层
def minSteps(nums):
end = 0 # 当前层的右边界
max_reach = 0 # 下一层能达到的最远位置
steps = 0
for i in range(len(nums) - 1): # 不遍历最后一个元素
max_reach = max(max_reach, i + nums[i])
if i == end:
steps += 1
end = max_reach
return steps适用场景： 这个模板适用于给定跳跃范围，求最少到达终点的步数的问题。本质上是 BFS 在一维区间上的优化实现——将 BFS 的”显式队列”优化为”区间端点”。
核心思想可推广到：
- 区间覆盖问题：给定多个区间，用最少数量的区间覆盖目标范围
- 最少跳跃次数：求”最少步数到终点”的通用解法
关联题目
- 55-跳跃游戏 — 同系列的判断版，只问能否到达，不问最少步数
- 1024-视频拼接 — 区间覆盖变体，可以将 clips 看作跳跃范围求最少拼接数
- 1326-灌溉花园的最少水龙头数目 — 经典区间覆盖问题，与本题跳跃思想一致
- 45-跳跃游戏II 与 55-跳跃游戏 的区别在于：前者保证可达求最少步数，后者判断是否可达