题目
给你一个非负整数数组 nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true；否则，返回 false。
示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
提示
一句话思路：贪心——维护「当前能到达的最远位置」，不断用每个可达位置的跳跃能力去延伸它。
- 关键性质：如果能到达某个位置，就一定能到达它前面的所有位置，所以只需维护一个最远可达下标
max_i。 - 遍历每个位置，只有
max_i >= i（当前位可达）且跳一下能更远时，才更新max_i。 - 最终如果
max_i能覆盖到最后一个下标，就说明可以到达。 - 一次遍历 O(n)，空间 O(1)。
答案
python
class Solution:
def canJump(self, nums):
max_i = 0 # 当前能到达的最远位置，初始在下标 0（自身一定可达）
for i, jump in enumerate(nums): # i 是当前位置，jump 是当前位置可跳的最大步数
if max_i >= i and i + jump > max_i: # 当前位置可达，且跳一下能到达更远
max_i = i + jump # 更新最远可到达的位置
return max_i >= i # 遍历结束时 i 是最后一个下标，能覆盖到即返回 True
留言板