学习目标

• 能把数组中的跳跃规则转化为可达性问题。
• 使用贪心策略维护扫描过程中能够到达的最远位置。
• 识别零步位置造成的不可达区间，并解释提前返回的条件。

前置知识

• 数组遍历与下标范围。
• max 函数和布尔值输出。
• 贪心算法中“保留当前最优状态”的思想。

问题描述

给定一个非负整数数组 nums，你最初位于数组的第一个下标。数组中的每个元素表示你在该位置可以跳跃的最大长度。

请判断是否能够到达数组的最后一个下标：如果可以，输出 true；否则输出 false。

例如，nums[i] = 3 表示从下标 i 最多可以跳到 i + 3，也可以选择跳更短的距离。

输入格式

• 第一行输入一个整数 n，表示数组长度。
• 第二行输入 n 个非负整数 nums[i]。

输出格式

如果能够到达最后一个下标，输出 true；否则输出 false。

约束

• 1 ≤ n ≤ 10^4。
• 0 ≤ nums[i] ≤ 10^5。
• 输入数组至少包含一个元素；长度为 1 时，起点就是终点。

示例

示例 1：可以到达

输入：

5
2 3 1 1 4

输出：

true

示例 2：被零步位置阻断

输入：

5
3 2 1 0 4

输出：

false

思路提示

从左到右扫描数组，维护当前能够到达的最远下标 maxReach。

• 如果当前下标 i > maxReach，说明它已经无法到达，后面的下标也不可能到达，直接返回 false。
• 如果当前下标可达，就用 max(maxReach, i + nums[i]) 更新最远位置。
• 扫描结束仍没有遇到不可达下标，就返回 true。

不要让“最远可达位置”被较小的新值覆盖；它只能保持不变或向右扩展。

复杂度分析

• 时间复杂度：O(n)，数组只扫描一次。
• 额外空间复杂度：O(1)。

运行与评分

在本 Lab 目录执行：

make doctor
make run
make score

如果没有 Make，也可以在仓库根目录执行：

pnpm lab:run -- labs/chapter-13/exercise/E-13-03-jump-game --target student

参考实现可以使用下面的命令验证：

pnpm lab:verify -- labs/chapter-13/exercise/E-13-03-jump-game --no-color

完成清单

• 正确读取数组长度和全部跳跃距离。
• 维护不会回退的最远可达位置。
• 遇到 i > maxReach 时返回 false。
• 正确处理单元素、零步障碍、恰好到达和提前到达终点等情况。
• 输出严格为小写 true 或 false。

思考与复盘

1. 为什么只记录最远可达位置，就足以判断后续位置是否可达？
2. 对于 [1, 1, 1, 0]，扫描到最后一个位置前，maxReach 如何变化？
3. 如果把 maxReach = max(maxReach, i + nums[i]) 错写成直接赋值，会出现什么问题？

题目来源

本题对应 LeetCode 55「跳跃游戏」：https://leetcode.cn/problems/jump-game/。