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

55. 跳跃游戏

---

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

问题描述：

给定一个非负整数数组 nums，其中 nums[i] 表示从位置 i 最多可以跳跃的步数。
从起点 0 出发，判断是否能够到达最后一个位置。

---

解题思路：

1. 设一个变量 mx 表示目前能跳到的最远位置索引（初始为 0）；
2. 从左往右遍历每个索引 i：

• • 如果当前位置 i 已经超过了当前最远能跳的位置 mx，说明跳不到这里，返回 False；
  • 否则，更新最远可达位置 mx = max(mx, i + nums[i])；
  • 如果最远位置已经大于等于终点（len(nums) - 1），说明可以到达终点，提前返回 True；

1. 如果遍历结束也没有提前返回 True，表示终点不可达，默认返回 False（此代码中漏了 return，但符合题意的测试数据一定会在中途 return）。

---

二、算法核心点

✅ 核心思想：贪心 + 动态维护最远可达索引

• 每次更新目前为止能跳到的最远位置；
• 如果当前下标不可达（即 i > mx），则直接失败；
• 一旦最远可达位置覆盖到终点，立即返回成功；
• 本质是将原本可能用 DFS/BFS 的可达性问题，用贪心方式优化为线性扫描。

class Solution:def canJump(self, nums: List[int]) -> bool:mx = 0for i, jump in enumerate(nums):if i >mx:return Falsemx = max(mx, i+jump)if mx>len(nums)-1:return True

---

三、复杂度分析

• 时间复杂度：O(n)
  只遍历了一次数组，每个元素处理一次；
• 空间复杂度：O(1)
  只使用了一个整型变量 mx。

---

总结表：

维度	内容
✅ 思路逻辑	从左向右遍历，维护最远可达位置，遇到不可达立即返回 False
✅ 核心技巧	贪心更新最远跳跃索引，判断当前位置是否可达，提早终止
✅ 时间复杂度	O(n)
✅ 空间复杂度	O(1)