55. 跳跃游戏（中等）

Blind 75 › 55. 跳跃游戏（中等） （第 2 章）
文章工具

题目

给定一个非负整数数组 nums，你一开始站在下标 0。位置 i 上的数字 nums[i]，表示从该位置起跳一次最多可以向右跳多少步（可以选 1 ~ nums[i] 中的任意步数）。

请判断：是否存在一种跳法，让你从下标 0 一路跳到最后一个下标 n - 1？能到就返回 true，否则返回 false。

自造示例 1：nums = [1,1,2,0,3] → true。走法：0 → 1（跳 1 步），1 → 2（跳 1 步），2 → 4（跳 2 步），到达终点。

自造示例 2：nums = [2,0,0,1,3] → false。从 0 最多只能到 1 或 2，而这两个位置的值都是 0，一旦落进去就再也走不动，到不了下标 4。

约束：数组长度 1 ~ 104；每个元素是 0 ~ 105 的整数。

思路

一句话：不需要记住具体路线，只要维护“目前最远能跳到哪”。

最直白的想法是把它当一张有向图：从 i 出发，能到 i+1, i+2, …, i+nums[i] 这些后继，然后用 BFS / DFS 看 0 能不能走到 n-1。这思路对，但慢在“每个位置都要展开一堆后继”，当很多位置的值都很大时，每个节点最多要连 O(n) 条边，整体可能退化到 O(n²)。动态规划 can[i] 逐个回看前面位置同理，也逃不掉 O(n²)。

关键观察：可达位置有一个非常整齐的性质——如果最远能到 reachable，那么 [0, reachable] 里的每个位置都一定可达。因为我们是从 0 开始一路向右扫描过来的，能更新出 reachable，中间就不会有断层。

于是问题从“记住每个点能否到”压缩成“维护一个右端点”：

  • 走到 i 时，若 i > reachable，说明这个位置已经落在

    🔒

    本篇为付费内容

    您已阅读试读部分，购买后即可解锁全文。

    ⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。