55. 跳跃游戏
一、算法逻辑（逐步思路）
问题描述：
给定一个非负整数数组 nums，其中 nums[i] 表示从位置 i 最多可以跳跃的步数。
从起点 0 出发，判断是否能够到达最后一个位置。
解题思路：
- 设一个变量
mx表示目前能跳到的最远位置索引（初始为 0）； - 从左往右遍历每个索引
i：
-
- 如果当前位置
i已经超过了当前最远能跳的位置mx，说明跳不到这里，返回False； - 否则，更新最远可达位置
mx = max(mx, i + nums[i])； - 如果最远位置已经大于等于终点（
len(nums) - 1），说明可以到达终点，提前返回True；
- 如果当前位置
- 如果遍历结束也没有提前返回
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) |
)
