55. 跳跃游戏 (Medium)
专题归类： 11-贪心 LeetCode 链接： https://leetcode.cn/problems/jump-game/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给你一个非负整数数组 nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度（即你可以跳 1 步到 nums[i] 步之间的任意长度）。
判断你是否能够到达最后一个下标，如果可以，返回 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，无法到达最后一个下标。
题目详细分析
数据范围： 1 <= nums.length <= 10^4，0 <= nums[i] <= 10^5
核心约束：
- 每个位置的值是最大跳跃长度，意味着可以跳
[1, nums[i]]步（或选择不跳，但必须前进） nums[i] = 0表示该位置是”死路”，跳到这里就无法继续前进- 只要存在一条路径能到最后一个下标即可，不需要最小步数
关键洞察：
- 不需要考虑具体怎么跳，只需关注”最远能到哪”
- 如果用可达性分析（BFS/DP），复杂度
O(n^2)，数据范围10^4勉强可行，但贪心O(n)更优 - 贪心能用的原因：如果能跳到位置 i，那么 i 之前的所有位置都是可达的——这是一种”区间覆盖”思想，不存在”跳过”某个位置的情况
小白版直白理解
就像过河踩着石头走，每块石头上标着”从这里你最多能往前跳多远”。你不需要每次都跳到最远，只要确保整条路上没有死胡同就行。
具体做法：你每走一步就抬头看看——“从现在的位置，最远能望到多远？“把这个最远距离记下来。如果你走到某一步发现，这个位置已经超出了你之前记下的最远距离，说明那里你根本到不了，游戏失败。
比如 [3,2,1,0,4]：从起点能跳 3 步，最远到下标 3；到了下标 3 发现这里只能跳 0 步，最远还是 3，到不了下标 4，所以失败。
解题思路
思路一：贪心——维护最远可达位置（推荐）
思路讲解： 遍历数组的每个位置，用一个变量 max_reach 记录当前能到达的最远位置。对于每个位置 i：
- 如果
i > max_reach，说明当前位置已经超出最远可达范围，返回false - 否则，用
i + nums[i]更新max_reach（取较大值） - 如果
max_reach >= n-1，说明最远已覆盖终点，返回true
为什么贪心是对的？因为如果能到位置 i，则 i 之前的所有位置都能到，所以维护最远距离这个”局部最优”等价于”全局最优”。
def canJump(nums):
max_reach = 0
n = len(nums)
for i in range(n):
if i > max_reach:
return False # 当前位置不可达
max_reach = max(max_reach, i + nums[i])
if max_reach >= n - 1:
return True # 已覆盖终点
return True时间复杂度： O(n) | 空间复杂度： O(1)
思路二：从后往前贪心
思路讲解： 逆向思考——从终点出发，看能否倒推到起点。用 last 表示当前需要被到达的位置（初始为最后一个下标），从右向左遍历：
- 如果
i + nums[i] >= last，说明从i可以到达last，于是将last更新为i - 最后判断
last == 0，即起点是否能间接到达终点
这个方法的好处是只需要一次逆向遍历，思想更直观。
def canJump(nums):
n = len(nums)
last = n - 1 # 需要被到达的位置
for i in range(n - 2, -1, -1):
if i + nums[i] >= last:
last = i # 更新需要被到达的位置
return last == 0时间复杂度： O(n) | 空间复杂度： O(1)
思路三：动态规划（备选）
思路讲解： 用 dp[i] 表示位置 i 是否可达。初始化 dp[0] = True，对于每个可达的位置 i，将 i+1 到 i+nums[i] 都标记为可达。虽然可解，但复杂度较高，仅作为思路扩展。
def canJump(nums):
n = len(nums)
dp = [False] * n
dp[0] = True
for i in range(n):
if dp[i]:
for j in range(1, nums[i] + 1):
if i + j < n:
dp[i + j] = True
return dp[n - 1]时间复杂度： O(n^2)（最坏） | 空间复杂度： O(n)
易错点
- 数组长度为 1：起点就是终点，直接返回
True。贪心写法需要确保在n=1时不会在循环中提前返回False nums[i] = 0的陷阱：位置 i 能否被安全跳过取决于它是否在max_reach范围内。如果 0 出现在中间并且max_reach能覆盖，依然可以到达终点- 更新
max_reach的顺序：必须先检查i > max_reach，再更新max_reach。如果先更新再检查，会错误地将不可达的位置标记为可达 - 反向遍历时
last的初始值：应设为n - 1，而不是n - 不要忽略大数溢出：
i + nums[i]可能超过n-1，这在 Python 中没问题，但在某些语言中需要注意
框架提炼
贪心模板：维护最远可达边界
def canReach(nums):
max_reach = 0
for i, step in enumerate(nums):
if i > max_reach:
return False
max_reach = max(max_reach, i + step)
if max_reach >= n - 1:
return True
return True适用场景： 给定一个跳跃/步长数组，问能否到达终点。核心思想是”能跳多远取决于最远的那一步”，将问题转化为区间覆盖问题——每个位置 i 覆盖区间 [i, i+nums[i]]，问这些区间能否拼接覆盖到终点。
这类问题的通用思路：
- 维护一个”当前可达的最远距离”
- 遍历位置，不断扩展这个距离
- 如果最远距离能覆盖终点，则成功
关联题目
- 45-跳跃游戏II — 保证能到达终点，求最少步数，用 BFS 思想的贪心
- 1306-跳跃游戏III — 每次只能向左或向右跳
nums[i]步，用 BFS/DFS 搜索 - 1024-视频拼接 — 区间覆盖问题的变体，同样可用贪心
- 1326-灌溉花园的最少水龙头数目 — 区间覆盖经典问题，与跳跃游戏 II 同源