🚀 力扣 45：跳跃游戏 II（全解法详解）
📌 题目描述
给你一个非负整数数组
nums，表示你最初位于数组的第一个位置。数组中的每个元素表示你在该位置可以跳跃的最大长度。
你的目标是使用 最少的跳跃次数 到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。
🎯 示例 1：
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到位置 1（跳 1 步），然后跳 4（再跳 1 步）——共 2 步
🎯 示例 2：
输入: nums = [2,3,0,1,4]
输出: 2
💡 解题思路总览
我们要找到 从起点跳到终点的最少步数。这题与「跳跃游戏 I」不同的地方是，这次我们不是判断“能否到达”，而是要求最小的“跳跃次数”。
✅ 解法一：贪心算法（最推荐🔥）
✨ 核心思路：
使用贪心思想，在每一步跳跃时，选择能跳的最远的那个位置。
🧠 实现步骤：
- 初始化步数
steps = 0，当前跳跃的边界end = 0，和当前最远位置farthest = 0 - 遍历数组：
- 每次更新当前最远能跳到的位置
- 当到达当前边界时，步数加一，并更新边界为
farthest
💻 代码实现（Go）：
func jump(nums []int) int {
steps := 0
end := 0
farthest := 0
for i := 0; i < len(nums)-1; i++ {
farthest = max(farthest, i+nums[i])
if i == end {
steps++
end = farthest
}
}
return steps
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
⏱️ 时间复杂度：O(n)
🧠 空间复杂度：O(1)
🔄 解法二：动态规划（自底向上）
✨ 核心思路：
定义 dp[i] 表示从位置 i 跳到终点所需的最小步数。
🧠 实现步骤：
- 初始化
dp[n-1] = 0（终点到终点步数为0） - 从右向左遍历数组
- 对于每个
i，从i+1到i+nums[i]找dp[j]中最小值
💻 代码实现（Go）：
func jump(nums []int) int {
n := len(nums)
dp := make([]int, n)
for i := n - 2; i >= 0; i-- {
minStep := int(1e9)
for j := i + 1; j <= i+nums[i] && j < n; j++ {
if dp[j] < minStep {
minStep = dp[j]
}
}
dp[i] = minStep + 1
}
return dp[0]
}
⏱️ 时间复杂度：O(n²)
🧠 空间复杂度：O(n)
💬 优点：清晰易懂，适合入门
❗ 缺点：效率较低，不适合数据量大的情况
🔁 解法三：反向贪心（从终点往回跳）
✨ 核心思路：
从终点出发，每次选择最靠前、但能够跳到当前终点的位置，更新目标点，直到回到起点。
🧠 实现步骤：
- 初始位置设为
pos = n-1 - 遍历数组从头找哪个位置能跳到
pos - 每次成功找到，就将
pos更新为当前索引，同时步数加一
💻 代码实现（Go）：
func jump(nums []int) int {
pos := len(nums) - 1
steps := 0
for pos > 0 {
for i := 0; i < pos; i++ {
if i+nums[i] >= pos {
pos = i
steps++
break
}
}
}
return steps
}
⏱️ 时间复杂度：O(n²)
🧠 空间复杂度：O(1)
💬 优点：逻辑反向，易于验证正确性
❗ 缺点：效率低，不适合大数据量
📊 三种方法对比总结
| 解法 | 时间复杂度 | 空间复杂度 | 适合场景 | 特点说明 |
|---|---|---|---|---|
| ✅ 贪心 | O(n) | O(1) | 面试首选 | 高效实用，核心技巧 |
| 动态规划 | O(n²) | O(n) | 教学/入门 | 思路清晰，但慢 |
| 反向贪心 | O(n²) | O(1) | 验证/反向思考 | 逆向推理，有趣但低效 |
📌 最佳实践建议
- 面试中建议优先写贪心算法，能体现算法思维和代码能力；
- 若初学 DP，可尝试动态规划方式，加深状态转移理解；
- 想换个角度思考，可尝试反向贪心，拓展思维维度。
📚 拓展阅读
- Leetcode 55. 跳跃游戏 I
- Leetcode 134. 加油站（贪心）
- Leetcode 122. 买卖股票的最佳时机 II（贪心）
💡 如果你觉得这篇文章对你有帮助，欢迎点赞 👍、收藏 ⭐、关注 📌，我将持续更新更多 LeetCode 热题的高质量解析～
