华为 OD 训练营 · 题解精讲
LC45. 跳跃游戏II
LC45. 跳跃游戏II
题目描述
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处: 0 <= j <= nums[i] i + j < n 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。 示例 1: 输入: nums = [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。 示例 2: 输入: nums = [2,3,0,1,4] 输出: 2 提示: 1 <= nums.length <= 10^4 0 <= nums[i] <= 1000
题目解析
解题思路
本题要求计算到达数组末尾的最小跳跃次数。参考代码采用贪心算法，核心思想是：在当前位置的可达范围内，选择下一次跳跃能到达最远位置的点作为下一跳位置，从而保证跳跃次数最少。
用到的数据结构：仅使用基本变量，无需额外数据结构。
核心逻辑：维护当前索引 nowPos，每次迭代中，先计算从当前位置能跳到的最远右边界 right = nowPos + nums[nowPos]。如果该右边界已覆盖或超过末尾，则直接返回 step + 1。否则，在区间 [nowPos+1, right] 内遍历，找出使 i + nums[i] 最大的索引 nextPos，作为下一次跳跃的位置。然后更新 nowPos = nextPos，步数加一，继续循环。
关键步骤
1. 判断是否可直接到达终点：若 right >= len(nums)-1，说明当前跳跃即可到达终点，返回 step + 1。 2. 寻找最优下一跳：遍历 [nowPos+1, right]，计算每个位置能到达的最远距离 i + nums[i]，记录最大值对应的索引 nextPos。 3. 更新状态：将 nowPos 设为 nextPos，step 加一，重复上述过程。
示意图（以 nums=[2,3,1,1,4] 为例）：
初始: nowPos=0, step=0
[2, 3, 1, 1, 4]
↑
right = 0+2 = 2
区间 [1,2] 中，i=1 时 i+nums[i]=4 最大 → nextPos=1
跳跃一次，nowPos=1, step=1
[2, 3, 1, 1, 4]
↑
right = 1+3 = 4 ≥ 4 → 返回 step+1 = 2复杂度分析
- 时间复杂度：O(n²)，最坏情况下每次跳跃只前进一个位置，内层循环遍历区间长度，总操作次数为 1+2+...+n ≈ O(n²)。但实际平均性能较好。
- 空间复杂度：O(1)，仅使用常数个变量。
参考代码
# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 添加微信 278166530 获取最新课程
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 跳跃游戏II（LeetCode 45）：https://leetcode.cn/problems/jump-game-ii/
class Solution:
def jump(self, nums: List[int]) -> int:
# 当前的位置，索引
nowPos = 0
# 最小的跳跃次数
step = 0
# nowPos 不断的调整位置
# 由于题目明确说明可以达到最后一个位置
# 因此，当 nowPos 超过或者等于 nums.length - 1 时
# 即跳出 while 循环，也就得到结果了
while nowPos < len(nums) - 1 :
# nowPos 对应的元素 nums[nowPos] 表示可以向后跳转的最大距离
# nowPos + nums[nowPos] 表示从 nowPos 跳跃一次，可以来到的最远的一个位置
# 这个位置也就是选择跳跃时的一个右边界
# 但不一定会选择跳到 nowPos + nums[nowPos] 这个位置
right = nowPos + nums[nowPos]
# 除非发现 right 可以到达末尾位置或者超过末尾位置
# 那么只需要在原来的 step 基础上跳跃一次即得到答案
if right >=len(nums) - 1 : return step + 1
# 否则就需要开始考虑下一次跳跃应该跳到 [ nowPos + 1 , right ] 之间的哪个位置
# 而选择的依据就是在上述区间选择的位置点，可以使得它的最大距离是所有选择中最大的
# 于是初始化两个变量
# nextRight 表示来到下一个跳跃点后，它的最大距离
nextRight = right
# nextPos 表示下一个跳跃点的位置
nextPos = nowPos
# 访问 [ nowPos + 1 , right ] 之间的元素
for i in range( nowPos + 1 , right + 1) :
# 不断更新最大距离
if i + nums[i] > nextRight :
# 不断更新最大距离
nextRight = i + nums[i]
# 不断更新跳跃点的位置
nextPos = i
# 跳出循环后，nextPos 就是跳跃的新位置
# nowPos 来到 nextPos 的位置
nowPos = nextPos
# 完成一次跳跃，setp 进行更新
step += 1
# 返回结果
return step