贪心算法题解——跳跃游戏 II【LeetCode】
45. 跳跃游戏 II
一、算法逻辑（逐步思路）
问题描述：
给定一个非负整数数组 nums，其中 nums[i] 表示从位置 i 最多可以跳跃的步数，起点在 0，终点在 n - 1。
目标是 使用最少的跳跃次数跳到终点，返回这个最小值。
解题思路：
- 维护两个变量：
-
cur_right：当前这次跳跃能到达的最远位置（当前“桥”右端）；next_right：下一次跳跃可能到达的最远位置（“下一座桥”右端）；ans：记录跳跃次数。
- 遍历数组的每个位置（注意 不遍历最后一个位置）：
-
- 不断更新下一次跳跃的最远位置，即
next_right = max(next_right, i + nums[i])； - 如果当前下标
i刚好到达了cur_right，说明当前跳跃范围已用完，必须跳一次，更新cur_right = next_right并ans += 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) |