题目描述题解一(贪心算法)(正向查找可到达的最大位置)(最优解)思路代码classSolution{publicintjump(int[]nums){// 如果数组长度只有1说明已经在终点不需要跳跃if(nums.length1)return0;intjumps0;// 记录跳跃次数intcurrentEnd0;// 当前这一跳能到达的最远边界intfarthest0;// 在当前边界内下一步能到达的最远极限// 注意这里遍历到 nums.length - 2 即可 (即 i nums.length - 1)// 因为如果当前边界 currentEnd 已经覆盖了最后一个元素就不需要再起跳了for(inti0;inums.length-1;i){// 沿途更新下一步能到达的最远距离farthestMath.max(farthest,inums[i]);// 如果走到了当前这一跳的边界说明必须进行下一次跳跃了if(icurrentEnd){jumps;// 跳跃次数 1currentEndfarthest;// 更新下一次跳跃的边界// 优化如果新的边界已经到达或超过终点直接结束if(currentEndnums.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){intpositionnums.length-1;// 当前需要到达的目标位置初始为终点intsteps0;// 记录跳跃次数// 当目标位置还没退回到起点 0 时继续反向查找while(position0){// 从左向右遍历寻找能到达当前 position 的最左侧最早位置for(inti0;iposition;i){if(inums[i]position){positioni;// 更新目标位置为这个起跳点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)。只使用了几个常数级别的额外变量