题目描述给定一个长度为n的数组nums初始位置在下标 0。每个元素nums[i]表示从索引i向后跳转的最大长度。返回到达n - 1的最小跳跃次数。测试用例保证可以到达n - 1。示例 1输入nums [2,3,1,1,4] 输出2 解释从下标 0 跳到下标 1跳 1 步再从下标 1 跳到下标 4跳 3 步示例 2输入nums [2,3,0,1,4] 输出2解题思路总览思路时间复杂度空间复杂度适用场景动态规划O(n^2)O(n)通用但慢BFSO(n^2)O(n)需要队列贪心反向O(n)O(1)最优解之一贪心正向O(n)O(1)最优解之一算法一动态规划思路dp[i]表示到达位置 i 所需的最小跳跃次数。转移方程dp[i] min(dp[j] 1)其中 j i 且 j nums[j] i代码classSolution{public:intjump(vectorintnums){intnnums.size();vectorintdp(n,INT_MAX);dp[0]0;for(inti1;in;i){for(intj0;ji;j){if(jnums[j]i){dp[i]min(dp[i],dp[j]1);}}}returndp[n-1];}};算法流程输入: nums [2,3,1,1,4], n5 dp[0] 0 i1: j0, 0nums[0]022 1, dp[1]dp[0]11 dp[1]1 i2: j0, 022 2, dp[2]dp[0]11 j1, 134 2, dp[2]min(1, dp[1]12)1 dp[2]1 i3: j0, 022 3, 不满足 j1, 134 3, dp[3]dp[1]12 j2, 213 3, dp[3]min(2, dp[2]12)2 dp[3]2 i4: j0, 022 4, 不满足 j1, 134 4, dp[4]dp[1]12 j2, 213 4, 不满足 j3, 314 4, dp[4]min(2, dp[3]13)2 dp[4]2 输出: 2复杂度分析复杂度分析时间复杂度O(n^2)- 两层循环空间复杂度O(n)算法二BFS思路从起点开始 BFS每一层代表一次跳跃遍历当前层所有能到达的位置更新下一层的可达范围。代码classSolution{public:intjump(vectorintnums){intnnums.size();intans0;intcurEnd0;// 当前跳跃的边界intnextEnd0;// 下一层跳跃的边界for(inti0;in-1;i){nextEndmax(nextEnd,inums[i]);if(icurEnd){ans;curEndnextEnd;}}returnans;}};算法流程输入: nums [2,3,1,1,4], n5 初始: ans0, curEnd0, nextEnd0 i0: nextEnd max(0, 02) 2 i curEnd(0), ans, ans1, curEnd nextEnd(2) 当前层结束跳跃次数1 i1: nextEnd max(2, 13) 4 i ! curEnd(2), 不做处理 i2: nextEnd max(4, 21) 4 i ! curEnd(2), 不做处理 i3: nextEnd max(4, 31) 4 i curEnd(2), ans, ans2, curEnd nextEnd(4) 当前层结束跳跃次数2 循环结束i 只到 n-23因为最后一步不需要再跳 curEnd(4) n-1(4)说明已经能到达终点 输出: ans 2复杂度分析复杂度分析时间复杂度O(n)- 每个位置只遍历一次空间复杂度O(1)算法三贪心反向查找思路从后往前找每一步找「能跳到当前位置」的最左边的位置直到起点。代码classSolution{public:intjump(vectorintnums){intans0;intposnums.size()-1;while(pos0){for(inti0;ipos;i){if(inums[i]pos){posi;ans;break;}}}returnans;}};算法流程输入: nums [2,3,1,1,4], n5, pos4, ans0 第一步: pos4, 从 i0 开始找能跳到 4 的位置 i0: 022 4, 不满足 i1: 134 4, pos1, ans1 找到跳到 pos1 第二步: pos1, 从 i0 开始找能跳到 1 的位置 i0: 022 1, pos0, ans2 找到跳到 pos0 pos0, 循环结束 输出: ans 2复杂度分析复杂度分析时间复杂度O(n)- 平均一次遍历最坏 O(n^2)空间复杂度O(1)算法四贪心正向最优解思路维护curEnd当前跳跃可达的边界和nextEnd下一次跳跃可达的最远位置。当遍历到curEnd时说明需要再跳一次ans并更新curEnd nextEnd。代码classSolution{public:intjump(vectorintnums){intans0;intcurEnd0;// 当前跳跃的右边界intnextEnd0;// 下一步能到的最远位置for(inti0;inums.size()-1;i){nextEndmax(nextEnd,nums[i]i);if(icurEnd){ans;curEndnextEnd;}}returnans;}};算法流程输入: nums [2,3,1,1,4] 初始: ans0, curEnd0, nextEnd0, n5 i0: nextEnd max(0, 02) 2 i(0) curEnd(0), ans (ans1), curEnd nextEnd(2) 第一次跳跃完成 i1: nextEnd max(2, 13) 4 i(1) ! curEnd(2), 不做处理 i2: nextEnd max(4, 21) 4 i(2) ! curEnd(2), 不做处理 i3: nextEnd max(4, 31) 4 i(3) curEnd(2), ans (ans2), curEnd nextEnd(4) 第二次跳跃完成 循环结束i 只到 n-23因为最后一步不需要再跳 输出: ans 2复杂度分析复杂度分析时间复杂度O(n)- 一次遍历空间复杂度O(1)复杂度对比总结思路平均时间最坏时间空间评价动态规划O(n^2)O(n^2)O(n)会超时BFSO(n^2)O(n^2)O(n)需要队列贪心反向O(n)O(n^2)O(1)最坏 O(n^2)贪心正向O(n)O(n)O(1)最优贪心正向核心思想nums [2,3,1,1,4] 遍历过程 ------------------------------------------------------------- | 下标 | 能跳到的最远 | curEnd | nextEnd | 跳跃次数 | | | 0 | 2 | 0 | 2 | 1 | 第一次跳 | | 1 | 4 | 2 | 4 | | 更新next | | 2 | 3 | 2 | 4 | | | | 3 | 4 | 2 | 4 | 2 | 第二次跳 | | 4 | - | - | - | | | ------------------------------------------------------------- 核心思想 - curEnd当前这一次跳跃能达到的最远边界 - nextEnd下一次跳跃能达到的最远边界 - 当 i 到达 curEnd 时必须再跳一次 - 每次跳跃 ans面试追问 FAQ问题回答为什么只需要遍历到n-1因为到达n-1不需要再跳最后一步是「落地」不是「跳跃」if (i curEnd)是什么意思当 i 到达当前跳跃的边界时必须再跳一次才能继续往前走如果nums[i] i比nextEnd还小max(nextEnd, nums[i] i)保证nextEnd总是取最大值这个算法和 BFS 有什么关系本质是 BFS 的层序遍历只是用两个变量代替了队列如果某个位置nums[i] 0怎么办如果i curEnd且i n-1说明卡住了但题目保证可达相关题目题目难度核心点55. 跳跃游戏中等判断能否到达本题的前置题45. 跳跃游戏 II中等求最小跳跃次数本题1306. 跳跃游戏 III中等带限制的跳跃总结项目内容核心思想贪心维护「当前边界」和「下一步最远」两个变量关键判断i curEnd 时需要再跳一次最优时间O(n)最优空间O(1)面试加分能解释这是 BFS 层序遍历的空间优化版本