🚀 LeetCode 热题 55：跳跃游戏（Jump Game）完整解析
📌 题目描述
给定一个非负整数数组
nums，你最初位于数组的第一个下标。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
🎯 示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：从位置 0 跳到位置 1（跳 1 步），然后跳 3 步到最后一个位置。
🎯 示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样都无法越过位置 3。
💡 解题思路
✅ 方法一：贪心法（Greedy）
- 核心思想：我们维护一个变量
maxReach表示当前能到达的最远位置。 - 每遍历一个位置
i，判断i是否在maxReach可达范围内。- 如果
i > maxReach：说明当前位置无法到达，直接返回 false。 - 否则，更新最远可达距离：
maxReach = max(maxReach, i + nums[i])。
- 如果
- 最后判断是否能到达末尾。
💻 Go 实现：贪心算法
func canJump(nums []int) bool {
maxReach := 0
for i := 0; i < len(nums); i++ {
if i > maxReach {
return false
}
maxReach = max(maxReach, i+nums[i])
}
return true
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
✅ 方法二：反向思维（从后往前跳）
- 从末尾开始找，看是否能“跳”回起点。
- 设置一个变量
lastPos，表示最早可以到达终点的位置。 - 倒序遍历数组，如果
i + nums[i] >= lastPos，说明可以从 i 位置跳到lastPos，更新lastPos = i。 - 最后判断
lastPos是否为 0，表示起点可达终点。
func canJump(nums []int) bool {
lastPos := len(nums) - 1
for i := len(nums) - 2; i >= 0; i-- {
if i+nums[i] >= lastPos {
lastPos = i
}
}
return lastPos == 0
}
🧠 方法对比
| 方法 | 优点 | 缺点 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|---|
| 贪心 | 简洁高效、一次遍历 | 无法记录路径 | O(n) | O(1) |
| 反向 | 更直观判断是否能跳回起点 | 不如贪心精简 | O(n) | O(1) |
⏳ 复杂度分析
- 时间复杂度： O(n)，只需遍历数组一次。
- 空间复杂度： O(1)，只用了常数级别的变量。
🎯 总结
- 本题的本质是动态规划的简化——局部最优推全局最优。
- 贪心策略是最快的解法：只关注“能跳到多远”。
- 如果面试中遇到此题，建议首选贪心法，简单高效。
- 💡 延伸题目：LeetCode 45. 跳跃游戏 II 是本题的进阶版本。
🧩 关键词回顾：
贪心算法、最远跳跃、局部最优、反向思维、动态规划简化、O(n) 时间复杂度
📌 如果你觉得这篇解析对你有帮助，欢迎点赞 👍、收藏 ⭐、评论 💬 交流，一起刷题进阶 🚀！
