题目描述给你一个非负整数数组nums你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。示例 1输入nums [2,3,1,1,4] 输出true 解释可以从下标 0 跳到下标 1再从下标 1 跳到最后一个下标示例 2输入nums [3,2,1,0,4] 输出false 解释无论怎样总会到达下标 3但该位置最大跳跃长度是 0无法到达最后一个下标解题思路总览思路时间复杂度空间复杂度适用场景模拟跳跃O(n)O(1)直观但繁琐BFSO(n)O(n)需要队列贪心O(n)O(1)本题最优解算法一模拟跳跃思路从起始位置模拟跳跃每次计算当前位置能跳到的最远距离逐个标记可以到达的位置。代码classSolution{public:boolcanJump(vectorintnums){intnnums.size();vectorboolcan(n,false);can[0]true;for(inti0;in;i){if(!can[i])returnfalse;intjumpnums[i];for(intji1;jmin(n-1,ijump);j){can[j]true;}}returncan[n-1];}};算法流程输入: nums [2,3,1,1,4] 初始: can[0] true i0: jump2, 能到达 [1,2] can[1]true, can[2]true i1: jump3, 能到达 [2,3,4] can[2]true, can[3]true, can[4]true i4: can[4]true, 到达终点 输出: true复杂度分析复杂度分析时间复杂度O(n^2)- 最坏情况下每个位置都要遍历其可达范围空间复杂度O(n)算法二BFS 广度优先搜索思路将每个位置看作图的一个节点从起点开始 BFS 遍历所有能到达的位置。代码classSolution{public:boolcanJump(vectorintnums){intnnums.size();queueintq;vectorboolvisited(n,false);q.push(0);visited[0]true;while(!q.empty()){intposq.front();q.pop();if(posn-1)returntrue;intjumpnums[pos];for(intj1;jjump;j){intnextposj;if(nextn)break;if(!visited[next]){visited[next]true;q.push(next);}}}returnfalse;}};算法流程输入: nums [2,3,1,1,4] 初始队列: [0] 取出 0: jump2, 加入 1,2 队列: [1,2] 取出 1: jump3, 加入 2,3,4 队列: [2,3,4] 取出 2: jump1, 加入 3 队列: [3,4] 取出 3: jump1, 加入 4 队列: [4] 取出 4: pos n-1, 返回 true复杂度分析复杂度分析时间复杂度O(n^2)- BFS 遍历每个可达位置空间复杂度O(n)算法三贪心最优解思路遍历数组维护一个maxlen表示当前能到达的最远位置。对于每个位置 i如果i maxlen说明当前位置根本到不了直接返回 false更新maxlen max(maxlen, i nums[i])即从 i 出发能到达的最远位置如果maxlen n-1说明已经能到达终点返回 true代码classSolution{public:boolcanJump(vectorintnums){intmaxlennums[0];intnnums.size();for(inti1;in;i){if(imaxlen)returnfalse;maxlenmax(maxlen,inums[i]);if(maxlenn-1)returntrue;}returntrue;}};算法流程输入: nums [2,3,1,1,4], n5 初始: maxlen nums[0] 2 i1: i(1) maxlen(2), 可以到达 maxlen max(2, 13) 4 maxlen(4) n-1(4)? 4 4, 返回 true 结果: true 输入: nums [3,2,1,0,4], n5 初始: maxlen nums[0] 3 i1: i(1) maxlen(3), 可以到达 maxlen max(3, 12) 3 i2: i(2) maxlen(3), 可以到达 maxlen max(3, 21) 3 i3: i(3) maxlen(3), 可以到达 maxlen max(3, 30) 3 i4: i(4) maxlen(3), 到达不了 返回 false复杂度分析复杂度分析时间复杂度O(n)- 只需一次遍历空间复杂度O(1)复杂度对比总结思路平均时间最坏时间空间评价模拟跳跃O(n^2)O(n^2)O(n)会超时BFSO(n^2)O(n^2)O(n)需要队列贪心O(n)O(n)O(1)最优贪心核心思想nums [2,3,1,1,4] 遍历过程 ------------------------------------------------------------- | 下标 | 能跳的距离 | 当前最远可达 | 是否可达 | | | 0 | 2 | 2 | 是 | | | 1 | 3 | 4 ↑ | 是 | 更新max | | 2 | 1 | 4 | 是 | | | 3 | 1 | 4 | 是 | | | 4 | 4 | 4 | 能到终点 | | ------------------------------------------------------------- 关键洞察 - maxlen 表示「从起点出发当前能到达的最远位置」 - 如果某个位置 i maxlen说明没有任何一个之前的位置能跳到 i - 一旦 maxlen n-1说明终点可达面试追问 FAQ问题回答为什么i maxlen就返回 false如果当前位置比最远可达位置还远说明没有任何位置能跳到这里i nums[i]是什么意思从位置 i 出发能跳到的最远位置 i 从 i 出发的最大跳跃长度如果第一个元素是 0 怎么办如果 nums[0] 0 且 n 1直接返回 false这个算法和「能跳到的最远距离」有什么关系核心就是维护「能跳到的最远距离」每步都更新这个上界相关题目题目难度核心点45. 跳跃游戏 II困难求最小跳跃次数55. 跳跃游戏中等判断能否到达本题1306. 跳跃游戏 III中等带限制的跳跃总结项目内容核心思想贪心维护「当前能到达的最远位置」关键判断i maxlen - 不可达最优时间O(n)最优空间O(1)面试加分能解释「最远距离」的递推关系
【力扣100题】95.跳跃游戏
题目描述给你一个非负整数数组nums你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。示例 1输入nums [2,3,1,1,4] 输出true 解释可以从下标 0 跳到下标 1再从下标 1 跳到最后一个下标示例 2输入nums [3,2,1,0,4] 输出false 解释无论怎样总会到达下标 3但该位置最大跳跃长度是 0无法到达最后一个下标解题思路总览思路时间复杂度空间复杂度适用场景模拟跳跃O(n)O(1)直观但繁琐BFSO(n)O(n)需要队列贪心O(n)O(1)本题最优解算法一模拟跳跃思路从起始位置模拟跳跃每次计算当前位置能跳到的最远距离逐个标记可以到达的位置。代码classSolution{public:boolcanJump(vectorintnums){intnnums.size();vectorboolcan(n,false);can[0]true;for(inti0;in;i){if(!can[i])returnfalse;intjumpnums[i];for(intji1;jmin(n-1,ijump);j){can[j]true;}}returncan[n-1];}};算法流程输入: nums [2,3,1,1,4] 初始: can[0] true i0: jump2, 能到达 [1,2] can[1]true, can[2]true i1: jump3, 能到达 [2,3,4] can[2]true, can[3]true, can[4]true i4: can[4]true, 到达终点 输出: true复杂度分析复杂度分析时间复杂度O(n^2)- 最坏情况下每个位置都要遍历其可达范围空间复杂度O(n)算法二BFS 广度优先搜索思路将每个位置看作图的一个节点从起点开始 BFS 遍历所有能到达的位置。代码classSolution{public:boolcanJump(vectorintnums){intnnums.size();queueintq;vectorboolvisited(n,false);q.push(0);visited[0]true;while(!q.empty()){intposq.front();q.pop();if(posn-1)returntrue;intjumpnums[pos];for(intj1;jjump;j){intnextposj;if(nextn)break;if(!visited[next]){visited[next]true;q.push(next);}}}returnfalse;}};算法流程输入: nums [2,3,1,1,4] 初始队列: [0] 取出 0: jump2, 加入 1,2 队列: [1,2] 取出 1: jump3, 加入 2,3,4 队列: [2,3,4] 取出 2: jump1, 加入 3 队列: [3,4] 取出 3: jump1, 加入 4 队列: [4] 取出 4: pos n-1, 返回 true复杂度分析复杂度分析时间复杂度O(n^2)- BFS 遍历每个可达位置空间复杂度O(n)算法三贪心最优解思路遍历数组维护一个maxlen表示当前能到达的最远位置。对于每个位置 i如果i maxlen说明当前位置根本到不了直接返回 false更新maxlen max(maxlen, i nums[i])即从 i 出发能到达的最远位置如果maxlen n-1说明已经能到达终点返回 true代码classSolution{public:boolcanJump(vectorintnums){intmaxlennums[0];intnnums.size();for(inti1;in;i){if(imaxlen)returnfalse;maxlenmax(maxlen,inums[i]);if(maxlenn-1)returntrue;}returntrue;}};算法流程输入: nums [2,3,1,1,4], n5 初始: maxlen nums[0] 2 i1: i(1) maxlen(2), 可以到达 maxlen max(2, 13) 4 maxlen(4) n-1(4)? 4 4, 返回 true 结果: true 输入: nums [3,2,1,0,4], n5 初始: maxlen nums[0] 3 i1: i(1) maxlen(3), 可以到达 maxlen max(3, 12) 3 i2: i(2) maxlen(3), 可以到达 maxlen max(3, 21) 3 i3: i(3) maxlen(3), 可以到达 maxlen max(3, 30) 3 i4: i(4) maxlen(3), 到达不了 返回 false复杂度分析复杂度分析时间复杂度O(n)- 只需一次遍历空间复杂度O(1)复杂度对比总结思路平均时间最坏时间空间评价模拟跳跃O(n^2)O(n^2)O(n)会超时BFSO(n^2)O(n^2)O(n)需要队列贪心O(n)O(n)O(1)最优贪心核心思想nums [2,3,1,1,4] 遍历过程 ------------------------------------------------------------- | 下标 | 能跳的距离 | 当前最远可达 | 是否可达 | | | 0 | 2 | 2 | 是 | | | 1 | 3 | 4 ↑ | 是 | 更新max | | 2 | 1 | 4 | 是 | | | 3 | 1 | 4 | 是 | | | 4 | 4 | 4 | 能到终点 | | ------------------------------------------------------------- 关键洞察 - maxlen 表示「从起点出发当前能到达的最远位置」 - 如果某个位置 i maxlen说明没有任何一个之前的位置能跳到 i - 一旦 maxlen n-1说明终点可达面试追问 FAQ问题回答为什么i maxlen就返回 false如果当前位置比最远可达位置还远说明没有任何位置能跳到这里i nums[i]是什么意思从位置 i 出发能跳到的最远位置 i 从 i 出发的最大跳跃长度如果第一个元素是 0 怎么办如果 nums[0] 0 且 n 1直接返回 false这个算法和「能跳到的最远距离」有什么关系核心就是维护「能跳到的最远距离」每步都更新这个上界相关题目题目难度核心点45. 跳跃游戏 II困难求最小跳跃次数55. 跳跃游戏中等判断能否到达本题1306. 跳跃游戏 III中等带限制的跳跃总结项目内容核心思想贪心维护「当前能到达的最远位置」关键判断i maxlen - 不可达最优时间O(n)最优空间O(1)面试加分能解释「最远距离」的递推关系
