贪心算法题解——跳跃游戏 II【LeetCode】

45. 跳跃游戏 II

---

一、算法逻辑（逐步思路）

问题描述：

给定一个非负整数数组 nums，其中 nums[i] 表示从位置 i 最多可以跳跃的步数，起点在 0，终点在 n - 1。
目标是 使用最少的跳跃次数跳到终点，返回这个最小值。

---

解题思路：

1. 维护两个变量：

• • cur_right：当前这次跳跃能到达的最远位置（当前“桥”右端）；
  • next_right：下一次跳跃可能到达的最远位置（“下一座桥”右端）；
  • ans：记录跳跃次数。

1. 遍历数组的每个位置（注意 不遍历最后一个位置）：

• • 不断更新下一次跳跃的最远位置，即 next_right = max(next_right, i + nums[i])；
  • 如果当前下标 i 刚好到达了 cur_right，说明当前跳跃范围已用完，必须跳一次，更新 cur_right = next_right 并 ans += 1。

1. 最后返回跳跃次数 ans，即可得到最少跳跃步数。

---

二、算法核心点

✅ 核心思想：贪心 + 层级跳跃区间划分

• 将整个跳跃过程视为“逐层建桥”，每一次跳跃把当前位置与能到达的最远端看作一个“可跳跃区域”；
• 当当前位置到达当前跳跃范围的尽头时，说明需要进行一次新的跳跃；
• 这其实就是BFS 的按层遍历思想的贪心实现版本：

• • 一层一跳，寻找下一层最远边界；
  • 不需要记录路径，只关心跳跃次数。

这也是这类跳跃问题中经典的 “区间推进”贪心模型。

class Solution:def jump(self, nums: List[int]) -> int:ans = 0cur_right = 0next_right = 0for i in range(len(nums)-1):next_right = max(next_right, i+nums[i])# 遍历的过程中，动态的更新记录 下一座桥的最远点if i == cur_right:  # 无路可走，必须建桥cur_right = next_right # 更新可以到达的最远距离ans += 1return ans

---

三、复杂度分析

• 时间复杂度：O(n)
  只遍历了数组一遍，且每个位置处理一次。
• 空间复杂度：O(1)
  只用了常数个变量（ans, cur_right, next_right）。

---

总结表：

维度	内容
✅ 思路逻辑	每次跳跃更新当前最远能到达的位置，到达边界后跳一次
✅ 核心技巧	贪心模拟 BFS 层级遍历，按“跳跃区间”更新跳数
✅ 时间复杂度	O(n)
✅ 空间复杂度	O(1)