LeetCode热题100里的第55题“跳跃游戏”我围观过不少面试记录这道题出现的频率高得离谱。但有意思的是评论区里每次都能看到有人争论“到底该跳几步才能最快到终点”有人说要倒着推有人说要DFS暴力试折腾半天写出来的代码又长又容易错。我今天想把这道题彻底拆开从最直觉的暴力思路开始一步步演化到最优的贪心解法把每一步的“为什么”讲清楚。不管是第一次刷题的新手还是准备面试想补强贪心算法的人这篇应该都能给你一些实在的东西。有一点先说明如果已经知道这题能用贪心做代码十几行就结束了但面试官大概率会追问“你怎么证明贪心是对的”。所以这篇不仅仅给代码更会把它背后的推导过程、常见的错误写法、容易踩的坑一次讲全。1. 题目到底在问什么先别急着写代码1.1 题面解读一个容易被误读的“最多”原题描述很简单给你一个非负整数数组nums你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。拆一下关键信息nums[i]表示的是“最多能跳多远”不是“必须跳多远”。比如nums[0] 3意味着从下标0可以跳到下标1、下标2、下标3中的任意一个位置。只要最终能到达n-1这个位置就算成功中间怎么跳的路径不关心。数组里可能出现00意味着从这个位置无法再往前走。“最多能跳多少”这个措辞几乎决定了所有解法方向。如果你把它理解成“当前步长是固定的”就会一头扎进DFS暴力枚举然后在超时的边缘反复试探。我习惯把这个模型换一种说法站在下标i你脚下有一个区间[i, i nums[i]]区间里的每个整数下标你都能一脚踩上去。题目就是在问从下标0的区间出发能不能通过不断跳进新的区间最终覆盖到n-1。这么一想问题的结构就清楚多了——它是一个“可达区间不断扩张”的问题。1.2 直觉失败的根源为什么DFS会超时大多数人看到这题的第一反应都是直接搜。从0开始先试跳1步再试跳2步如果都到不了终点就回溯再试。逻辑非常直白代码也很好写def canJump(nums): n len(nums) def dfs(pos): if pos n - 1: return True for step in range(1, nums[pos] 1): if dfs(pos step): return True return False return dfs(0)这段代码在面试现场写出来你的思路是清晰的但问题在于它太慢了。最坏情况下比如nums [n-1, n-2, ..., 1]每个位置都几乎能跳到后面所有位置搜索树会以一种恐怖的速度膨胀。状态空间是组合级别的指数爆炸。更要命的是这个递归里存在大量重复子问题dfs(i)可能被从不同路径调用几十次每次都要重新展开一整棵子树。这种“算了又算”的浪费恰好是动态规划登场的信号。所以与其说这题考察的是暴力搜索能力不如说它在考察你能不能一眼看穿递归背后的重复结构并设计出避免重复计算的方案。2. 从暴力到动态规划把重复计算干掉2.1 自顶向下记忆化给DFS加个缓存规避重复子问题最直接的方式就是把已经算出来的结果存下来下次直接查表。这就成了自顶向下的动态规划或者叫“记忆化递归”。定义状态dp[i]表示从下标i出发是否能够到达终点。转移逻辑和DFS完全相同dp[i] 是否存在 j ∈ (i, inums[i]]使得 dp[j] true递归出口是i n-1时直接返回true。from functools import lru_cache class Solution: def canJump(self, nums: List[int]) - bool: n len(nums) lru_cache(None) def dfs(i): if i n - 1: return True farthest min(n - 1, i nums[i]) for j in range(i 1, farthest 1): if dfs(j): return True return False return dfs(0)加了个缓存时间复杂度从指数级降到O(n * max(nums[i]))每个位置最多被计算一次每次计算最多枚举nums[i]个后继位置。空间复杂度O(n)用来存递归栈和缓存。这个版本在LeetCode上已经能通过了但它不是最优。你可以在面试里把它作为“优化过程中的一步”展示别直接拿来当最终答案因为面试官几乎必然会问“能不能再优化”。2.2 自底向上DP把递归改成填表递归能改循环记忆化能改递推。把状态转移倒过来从终点往回填表就得到了自底向上的动态规划。class Solution { public boolean canJump(int[] nums) { int n nums.length; boolean[] dp new boolean[n]; dp[n - 1] true; for (int i n - 2; i 0; i--) { int farthest Math.min(n - 1, i nums[i]); for (int j i 1; j farthest; j) { if (dp[j]) { dp[i] true; break; } } } return dp[0]; } }填表的顺序是从右往左最后一个位置肯定是true然后看它左边的位置如果某个位置能跳到true的位置那它自己也是true。这个版本的复杂度仍然是O(n * max(nums[i]))在数据弱的时候能过但严格来说不是这题的“标准答案”。你拿这版去面试如果面试官懂行一定会引导你往O(n)想。从暴力搜索到记忆化再到填表这个递进过程的价值在于它帮你建立了“动态规划是怎么从暴力优化出来的”这一整套认知。但跳跃游戏这题真正的精华其实是下面这个跳过了DP的贪心思维。3. 贪心解法把问题变成“最远可达距离的维护”3.1 核心思路maxReach 是怎么诞生的顺着“可达区间不断扩张”这个模型往下想我根本不需要知道每个位置具体能不能到我只需要维护一个变量——目前所有可达位置中能跳到的最远下标。用maxReach表示这个最远下标。初始时站在下标0maxReach 0 nums[0]。然后从左往右扫描每个下标i如果i maxReach说明当前位置已经超出了所有可达范围的边界连站都站不上去直接返回false。否则位置i是可达的那么从i出发可以扩展新的可达范围到i nums[i]更新maxReach max(maxReach, i nums[i])。一旦maxReach n-1说明终点已经在可达范围内返回true。举个例子nums [2, 3, 1, 1, 4]初始maxReach 0 2 2说明下标0、1、2都在可达范围内。扫描到i 1maxReach max(2, 1 3) 4直接覆盖终点返回true。整个过程只扫了一遍数组时间复杂度O(n)空间复杂度O(1)。这就是这道题的最优解也是面试官最想听到的方案。3.2 正确性证明为什么不需要回溯写贪心的人最怕的一件事就是局部最优不等于全局最优。但跳跃游戏这个贪心是安全的原因在于它的“最优子结构”异常简单。可以用归纳法来论证扫描到下标i时maxReach表示的是“从起点出发通过任意合法跳跃组合能够到达的最远下标”。因为maxReach是连续区间覆盖的右边界所以任意j maxReach的位置都是可达的——这保证了“只要i maxReach位置i一定可达”的正确性。位置i可达后i nums[i]是一个新的候选跳跃终点用它更新maxReach新的maxReach依然是全量可达位置中的最远值。归纳推进直到扫描完整个数组或提前覆盖终点。关键点在于只要有路径能到达maxReach覆盖的范围内就一定能到达该范围内的任意一个具体下标。跳跃的“最大长度”定义赋予了这个区间连续性中间不存在断点。所以不需要回溯不需要记录路径一个整数足矣。这也是为什么这个解法写出来只有十几行却很难被挑出毛病。3.3 代码实现Java/Python/Go 三版贪心解法我用三种常用语言各写一遍方便对照着抄作业。Javaclass Solution { public boolean canJump(int[] nums) { int n nums.length; int maxReach 0; for (int i 0; i n; i) { if (i maxReach) { return false; } maxReach Math.max(maxReach, i nums[i]); if (maxReach n - 1) { return true; } } return true; } }Pythonclass Solution: def canJump(self, nums: List[int]) - bool: n len(nums) max_reach 0 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 TrueGofunc canJump(nums []int) bool { n : len(nums) maxReach : 0 for i : 0; i n; i { if i maxReach { return false } if inums[i] maxReach { maxReach i nums[i] } if maxReach n-1 { return true } } return true }三种写法逻辑完全一致区别只在语言语法。这里多提一句循环里的if (maxReach n-1) return true是提前返回的优化不加它也可以只是会多一些无意义的扫描。加了之后在理想情况下能省不少时间。另外力扣官方题解里还写过一种从右往左的贪心把“能否到达终点”转化成“终点能否被不断前移”维护一个last表示当前需要被到达的最左位置从右往左扫描如果i nums[i] last说明i能到达 last把last更新为i。最终检查last是否归零。这两种写法本质等价面试时挑一种你顺手的讲清楚就行不用两个都背。4. 易错点与边界条件这些坑我真的踩过4.1 边界问题长度1、全零数组、恰好跳满边界条件是面试官最爱塞的小陷阱也是自己写题时最容易翻车的地方。我把跳跃游戏里几个典型的边界情况整理了一下用例预期结果原因分析[0]true只有一个位置已经在终点[1, 0]true从0跳1步正好落在终点[0, 1]false起点nums[0] 0一步都动不了[2, 0, 0]true从0跳2步直接到终点[1, 0, 0]false从0跳1步到位置1nums[1]0卡死[3, 2, 1, 0, 4]false位置3是0前面所有路都被它截断第一个用例[0]是最容易写错的很多人一看nums[0] 0就直接返回false却忘了数组长度是1时你已经在终点了。所以代码里要么在循环外先判断n 1要么保证循环逻辑天然兼容长度为1的情况。上面给的三版代码都不用特殊处理因为maxReach 0maxReach n-1 0直接返回true。[1, 0]这个用例也经常有人纠结从0只能跳1步跳到1之后nums[1] 0动不了但1就是终点啊。所以别把“nums[i] 0”直接理解成“死路”它只是“当前位置无法继续前进”如果它恰好是终点那照样返回true。4.2 代码细节更新顺序和提前返回的时机贪心解法看起来简单但细节里藏着一个容易写错的地方先判断当前位置可达还是先更新maxReach以[2, 0, 0]为例。当i 1时maxReach还是2i maxReach没问题当i 2时maxReach已经被更新为2i依然不大于它。但如果把判断顺序写反先更新maxReach再判断i是否可达可能在当前位置根本不可达的情况下依然用它的nums[i]去扩展范围造成“幽灵跳跃”。正确顺序一定是先判断是否卡住i maxReach则返回false再更新maxReach最后判断是否提前结束。这个顺序不能调换。还有个细节是maxReach Math.max(maxReach, i nums[i])里的Math.max。有些新手喜欢直接写maxReach i nums[i]这会把历史可达范围丢掉。比如[2, 1, 0, 3]扫描到i 1时如果直接赋值maxReach 1 1 2而历史值本来就是2这里没区别但遇到[5, 1, 0, 3]这种数组扫描到i 1时直接赋值会从5缩水到2后面的i 3就变成不可达了真实情况是下标3完全没问题。所以max操作必须保留。4.3 测试用例设计怎么设计一组能证明你写对的用例刷题和面试写题都有个习惯代码写完别急着提交先在脑子里跑几个用例。我常用的测试集是这么设计的最简单的前进型[1, 1, 1]应该返回 true。起点卡死型[0, 2, 3]返回 false因为第一步都迈不出去。中途断档型[1, 0, 1]返回 false位置1是0过不去。大跳跃型[10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]第一个位置直接到终点返回 true。经典困难型[3, 2, 1, 0, 4]返回 false。自身长度1[0]、[5]都返回 true。这套用例覆盖了“长度为1”、“恰好到达”、“起点阻塞”、“中途断档”、“大跨度直接覆盖”五类情况。写完代码后在脑内逐行模拟一遍基本上提交时一次过的概率会高很多。5. 从跳跃游戏到跳跃游戏II贪心的进阶用法5.1 最少步数版本的思路LeetCode热题100里还有一道“跳跃游戏II”第45题问题和这题几乎一样只是把“能否到达”换成了“最少需要跳几次”。这俩放一起刷效果特别好因为能看同一个贪心模型怎么演变。第45题的思路依然是维护可达区间但多了一个“步数计数”的维度。你需要三个变量maxReach当前扫描过程中能达到的历史最远位置。currentEnd当前这步跳跃最多能到达的边界。steps当前已经使用的跳跃次数。每次扫描位置i时更新maxReach当i到达currentEnd说明必须再跳一次才能继续前进于是把currentEnd更新为maxReachsteps加一。最终返回steps。对比一下两题就能发现判定版只需要“覆盖不断扩张”这一个不变量计数版则额外需要“分层的边界”。题45其实是把这个贪心模型用到了更复杂的场景里理解了题55题45的代码基本就是顺水推舟。5.2 面试官会怎么追问四个方向的延伸我在模拟面试和实际面试里被问过关于这题的很多变形挑几个有代表性的分享追问1为什么贪心是正确的这就是我前面讲的连续性论证。面试官真正想看的是你有没有理解“可达范围是一个连续区间”而不是死记硬背解法。追问2如果数组特别大怎么办这题的贪心解法空间复杂度是O(1)根本不需要额外数组。很多人一上来就写DP数组面试官追问空间优化时会卡壳所以动手前多问自己一句“这个状态真的需要记录吗”。追问3把“最多跳nums[i]步”改成“必须跳恰好nums[i]步”呢那就不是区间覆盖问题了变成一个严格的路径搜索可能需要BFS或者图的最短路模型。可以看到“最多”和“恰好”这两个词对问题性质的影响是巨大的。追问4允许往左跳呢问题立刻变成图模型原题里“只往右跳”的区间贪心全部失效常规做法是BFS最短路。这类变体题在周赛里经常出现比如带传送门的跳跃问题核心是识别出“图”这个本质。5.3 相关变体题一图流顺着“跳跃”这个主题LeetCode上还有几道可以连起来刷的题题号题目与本题的关系45跳跃游戏II求最少步数贪心的进阶版1306跳跃游戏III可以双向跳图论BFS1345跳跃游戏IV有值相同的传送门图的BFS1696跳跃游戏VI带权值且求最大得分需要优先队列优化DP建议刷题顺序是55 → 45 → 1306 → 1345。这样你能体验同一类模型从贪心到DP再到图的逐步抽象过程比单纯背题有效得多。6. 我的实战心得与刷题建议6.1 拿到一道题我的思考路径是什么很多初学者拿到题就直接敲代码这个习惯不太好。我一般会按下面几个问题来组织思路这个问题的输入是什么输出是什么能不能用一个小的例子先模拟一遍。这题是“存在性判定”问题还是“最优值求解”问题存在性判定经常有贪心或DFS两种路线最优值求解则大概率是DP或二分。如果使用暴力搜索是否存在重复子问题如果存在能不能用DP优化。在DP的基础上状态转移里有没有“不需要完整状态”的信息可以压缩跳跃游戏恰好每一步都能用这套框架来验证它是个存在性判定暴力会重复计算DP需要整个数组但“可达区间连续性”这个性质让我意识到一个maxReach变量就够了。这种思考链条才是刷题真正的肌肉记忆。把数组模拟成“一个个区间”的意识特别重要。数组题里很多所谓的“难题”本质都是在扫描过程中维护某个边界或极值。不是只有跳跃游戏这样像连续子数组最大和、盛最多水的容器、合并区间背后都有类似的区间思维。6.2 给刷题新手的几个具体建议第一千万别把答案背下来。跳跃游戏的解法很短背下来花不了三分钟但下次遇到“跳跃游戏VI”你就会发现自己根本不知道从哪里下手。理解“不变量”比记住代码重要得多。第二写题前先想清楚边界。我见过太多人提交之后挂在[0]这种用例上。写代码之前先问自己三个问题数组长度最小是多少第一个元素是0会怎样所有元素都是0会怎样第三刷完一题后至少做一次“变体联想”。可以自己改改条件试试比如把数组改成环形、把跳跃改成固定步数、把判定改成求最大覆盖范围。这种玩法对培养解题直觉的帮助是巨大的。第四面试时一定要边说边写。你的思考过程比代码本身更值钱。比如写完maxReach Math.max(...)之后主动补一句“这里用max是因为我不能丢掉历史最优的覆盖范围否则后面可能出现假性断档”面试官对你的评价会明显不一样。6.3 关于这道题的一些额外体会题55在LeetCode热题100里的地位挺特别的它不考什么复杂数据结构不考高深算法模板纯粹考察你有没有把“暴力思维”升级成“贪心思维”的敏感度。很多人刷题刷了大几百道遇到这题照样会陷入“每一步怎么选最优”的迷惑本质原因就是没有想清楚“最多跳”和“可达区间”之间的等价关系。我自己第一次做这题时还干过一件蠢事开了一个二维布尔数组存dp[i][j]表示“能不能从i跳到j”写完发现空间复杂度直接爆炸代码又臭又长。后来想明白这个问题的状态根本不需要那么细才真正体会到“关注本质信息”这句话的分量。如果让我用一句话总结这道题我会说它不是一道让你模拟跳跃的题而是一道让你维护“最大覆盖范围”的题。想清楚这一层代码就是顺水推舟的事。希望这篇拆解能帮你把这道经典题彻底吃透。