45.跳跃游戏Ⅱ

题目描述

题解一(贪心算法)(正向查找可到达的最大位置)(最优解)

思路

代码

classSolution{publicintjump(int[]nums){// 如果数组长度只有1，说明已经在终点，不需要跳跃if(nums.length<=1)return0;intjumps=0;// 记录跳跃次数intcurrentEnd=0;// 当前这一跳能到达的最远边界intfarthest=0;// 在当前边界内，下一步能到达的最远极限// 注意：这里遍历到 nums.length - 2 即可 (即 i < nums.length - 1)// 因为如果当前边界 currentEnd 已经覆盖了最后一个元素，就不需要再起跳了for(inti=0;i<nums.length-1;i++){// 沿途更新下一步能到达的最远距离farthest=Math.max(farthest,i+nums[i]);// 如果走到了当前这一跳的边界，说明必须进行下一次跳跃了if(i==currentEnd){jumps++;// 跳跃次数 +1currentEnd=farthest;// 更新下一次跳跃的边界// 优化：如果新的边界已经到达或超过终点，直接结束if(currentEnd>=nums.length-1){break;}}}returnjumps;}}

复杂度分析

• 时间复杂度：O(N)O(N)O(N)。其中NNN是数组 nums 的长度
• 空间复杂度：O(1)O(1)O(1)。整个算法执行过程中，我们仅仅声明了三个整型变量（jumps、currentEnd、farthest）来记录状态。无论输入的数组 nums 有多长，我们所需的额外内存空间都是固定不变的

题解二(贪心算法)(反向查找出发位置)

思路

代码

classSolution{publicintjump(int[]nums){intposition=nums.length-1;// 当前需要到达的目标位置，初始为终点intsteps=0;// 记录跳跃次数// 当目标位置还没退回到起点 0 时，继续反向查找while(position>0){// 从左向右遍历，寻找能到达当前 position 的最左侧（最早）位置for(inti=0;i<position;i++){if(i+nums[i]>=position){position=i;// 更新目标位置为这个起跳点steps++;// 跳跃次数 +1break;// 已经找到了最左侧的，跳出 for 循环，开始新一轮的 while 寻找}}}returnsteps;}}

复杂度分析

• 时间复杂度：O(N2)O(N^2)O(N2)。在最坏的情况下（例如数组是 [1, 1, 1, 1, 1]），我们每次都只能往左退一步。为了退这一步，for 循环要从 0 遍历到 position - 1。总的遍历次数大约是(N−1)+(N−2)+⋯+1(N-1) + (N-2) + \dots + 1(N−1)+(N−2)+⋯+1，属于O(N2)O(N^2)O(N2)级别
• 空间复杂度：O(1)O(1)O(1)。只使用了几个常数级别的额外变量