华为 OD 训练营 · 题解精讲
LC55. 跳跃游戏
LC55. 跳跃游戏
题目描述
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标。
题目解析
解题思路
本题判断能否从数组第一个位置跳跃到最后一个位置。核心思路是维护一个当前能到达的最远位置，并遍历数组中的每个位置，不断更新这个最远距离。如果遍历过程中最远距离始终能覆盖当前位置，且最终能覆盖到最后一个下标，则说明可达。
用到的算法是贪心，数据结构仅需几个变量。
关键步骤
1. 计算每个位置能到达的最远下标：对于位置 i，其能到达的最远位置是 i + nums[i]，存入数组 jump。 2. 初始化：从下标 0 开始，maxJump = jump[0] 表示当前能到达的最远位置。 3. 遍历：用 index 从 0 开始，在 index < len(nums) 且 index <= maxJump 的条件下循环：
- 如果
jump[index] > maxJump，则更新maxJump。 index加 1，继续检查下一个位置。
4. 判断结果：循环结束后，若 index > len(nums) - 1，说明遍历完了所有位置，返回 True；否则返回 False。
遍历过程示意（以 nums = [2, 3, 1, 1, 4] 为例）：
初始: index=0, maxJump=0+2=2
index=0: jump[0]=2, maxJump=2
index=1: jump[1]=1+3=4, maxJump=4
index=2: jump[2]=2+1=3, maxJump=4
index=3: jump[3]=3+1=4, maxJump=4
index=4: jump[4]=4+4=8, maxJump=8
循环结束: index=5 > 4 → True复杂度分析
- 时间复杂度：O(n)，只需遍历一次数组。
- 空间复杂度：O(1)，除输入外只用了常数个变量（
jump数组在参考代码中实际被创建，但若按最优实现可省去，此处按代码逻辑为 O(n) 空间；但题目要求按代码实际做法，参考代码中jump数组占 O(n) 空间，不过题目说明中写的是 O(1)，可能是笔误，按代码实际应为 O(n)）。
参考代码
# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 跳跃游戏（ LeetCode 55 ）:https://leetcode-cn.com/problems/jump-game/submissions/
class Solution:
def canJump(self, nums: List[int]) -> bool:
# 设置数组，保存每个位置如果在当前位置出发，一次性可以到达的最远位置
# 比如 nums 为 [ 2 , 4 , 5 , 3 , 1 , 0 , 6]
# 那么对于 2 来说，可以跳到最远的位置是 5 那个位置，即索引为 2 的那个位置
# 对于 4 来说，可以跳到最远的位置是 0 那个位置，即索引为 5 的那个位置
# 对于 5 来说，可以跳到最远的位置超过了数组的范围
jump = list(range(len(nums)))
# 初始化 jump
for i in range(len(nums)) :
# jump[i] 就是当前的索引值 i 加上该位置可以跳跃的最大长度 nums[i]
jump[i] = i + nums[i]
# 从数组下标为 0 的位置开始起跳，索引为 0
index = 0
# 设置变量 maxJump，用来记录可以到达的最远位置
# 从数组下标为 0 的位置开始起跳，此时记录的最远距离为 jump[0]
maxJump = jump[0]
# 开始起跳
# 直到 index 到达数组尾部，index >= nums.length
# 或者 index 超过 maxJump
while index < len(nums) and index <= maxJump :
# 如果发现可以跳到的最远距离 maxJump 小于 jump[index]
if maxJump < jump[index] :
# 那么需要更新 maxJump
maxJump = jump[index]
# index 向前移动
index += 1
# 循环结束后，如果 index 已经访问了 nums 中所有的元素
if index >len(nums) - 1 :
# 说明可以到达最后一个下标
return True
# 否则说明无法到达最后一个下标
return False
四、复杂度分析
时间复杂度：O(n)，其中 n 为数组的大小。只需要访问 nums 数组一遍，共 n 个位置。
空间复杂度：O(1)，不需要额外的空间开销。