跳跃游戏
Jump Game
从下标 0 出发，每格数字是能跳的最远长度，判断能否到达最后一个下标。
在力扣中练习题目描述
给你一个非负整数数组 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 ， 所以永远不可能到达最后一个下标。
提示：
1 <= nums.length <= 1040 <= nums[i] <= 105
解题思路
贪心 · 维护最远可达
不关心怎么跳，只关心最远能覆盖到哪
不需要枚举每一种跳法。扫描时维护所有已到达位置能覆盖的最远下标 maxReach，它概括了当前所有选择的能力。
自拟主例 [2,3,1,0,2,0,0,1] 会返回 false。前面的 0 可以跨过：下标 1 已把覆盖范围推进到 4，下标 3 跳不动也不影响继续检查下标 4。
站在 1，可尝试到 4：覆盖范围 2 → 4。
- maxReach
- 4
只有 i <= maxReach 时，当前位置才可使用，再更新 max(maxReach, i+nums[i])。如果先更新，就会借用根本走不到的位置，把失败误判为成功。
站在 5，可尝试到 5：覆盖范围 6 → 6。
单个 0 不是失败条件，关键看更早的位置是否已经覆盖它的后方。
- maxReach
- 6
主例最后只能覆盖到 6，下标 7 即使值为 1，也已经不可达。遇到这种断档立即返回 false；若覆盖范围已包含终点，则可以立即返回 true。
易错点
- 先更新 maxReach 再判断 i > maxReach：所有位置都会被自己救活，[0,1] 会误判为 true。
- maxReach 写成 i + nums[i] 直接赋值，丢掉 max —— 遇到 nums 变小时可达范围会被不必要地收窄。
- 把 nums[i] 当成「体力」一路累加，跳跃是选一次落点，不是每天恢复步数。
逆向贪心
从终点往回看：谁能跳到我，就把目标挪过去
同样是 O(n) 的正确贪心，从后向前维护目标位置，可与主解法的覆盖范围对照。
正着推是「我能到哪」，倒着推是「谁能到我」。
把 last 设成「目前必须能到达的位置」，初始为终点 n - 1。从右往左扫描，如果 i + nums[i] >= last，说明从 i 能直接跳到（或越过）目标，那么只要 i 可达，目标就一定可达 —— 于是把目标左移到 i，继续往前找。
扫到下标 0 时，如果 last == 0，说明「能到达终点的链条」一路接到了起点，返回 true。
这个写法不需要维护区间，只有一个 last 变量，逻辑上更接近「倒推」。代价是不太好处理「提前结束」的优化，必须扫完整个数组，但复杂度同样是 O(n)。
两种贪心的共同点是：都在利用「可达位置是连续区间」这个性质，只是一个从左边扩张区间，一个从右边收缩目标。
- 1last 初始化为最后一个下标，表示当前的目标位置。
- 2从右往左枚举 i。
- 3若 i + nums[i] >= last，说明 i 能跳到目标，last 左移到 i。
- 4扫描结束后，last == 0 表示从起点出发能接上这条链。
易错点
- 循环写成 i > 0，漏掉下标 0 这一格：[2,0,0] 这种只能从起点一步到终点的数组会误判成 false。
- 把条件写成 i + nums[i] == last，只能跳「正好」，越过目标其实也算到达。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
nums = [2, 3, 1, 0, 2, 0, 0, 1]从下标 0 出发，maxReach=0；只使用确实可到达的位置更新覆盖范围。
查看 C++ 代码
延伸阅读
- 「可达位置是连续区间」是覆盖类贪心的核心性质，跳跃游戏 II（45）求最少步数、视频拼接（1024）都建立在它上面。
- 求最少步数时，贪心要改成按层扩张：维护当前层的右边界和下一层能到的最远位置，层数就是步数。
- 如果允许向左跳，区间性质就不成立了，必须退回到 BFS / 最短路那一套。