核心内容摘要
InstructPix2Pix动态演示：一张图教你玩转AI修图
跳跃游戏 II | 贪心算法最优解最少跳跃次数题目描述给定一个长度为n的 0 索引整数数组nums初始位置为数组下标 0。
数组中每个元素nums[i]表示从下标i处可以向前跳跃的最大长度即若处于索引i可跳跃到任意满足i j n且j ≤ i nums[i]的索引j。
要求返回到达数组最后一个下标n-1的最小跳跃次数题目保证一定可以到达最后一个下标。
核心特征分析数组类问题的算法选择优先级贪心算法 动态规划尤其当问题仅需“最优结果”而非“所有路径”时本题中“每个元素代表可跳跃的最大长度”是贪心算法的典型适配场景——无需记录所有跳跃路径只需通过“局部最优选择”即可推导“全局最优解”最少跳跃次数。
算法选择与思路算法选择选择贪心算法作为最优解核心原因如下动态规划需维护数组记录每个位置的最少步数时间复杂度O ( n 2 ) O(n^
O(n
、空间复杂度O ( n ) O(n)O(n)效率较低贪心算法仅需常数级变量记录关键状态时间复杂度O ( n ) O(n)O(n)、空间复杂度O ( 1 ) O(
O(
且能直接推导最少跳跃次数是本题的最优解法。
贪心算法核心思路关键变量定义step记录已完成的跳跃次数current当前跳跃范围内能到达的最远边界即本次跳跃的“终点”max_length遍历过程中能到达的全局最远索引所有可达位置中能跳的最远位置。
算法执行步骤初始化step
current
max_length 0补充边界处理若数组长度≤1无需跳跃直接返回0遍历数组中的每个索引i刷新全局最远可达索引max_length max(max_length, i nums[i])若i current遍历到当前跳跃的边界说明必须完成一次跳跃① 跳跃次数加1step② 更新下一次跳跃的边界current max_length若current ≥ n-1当前边界已覆盖最后一个下标提前终止遍历无需继续计算遍历结束后返回step。
完整解题代码classSolution{public:intjump(vectorintnums){intnnums.size();// 边界处理数组长度≤1时初始位置即为终点无需跳跃if(n
return0;intstep0;// 最少跳跃次数intcurrent0;// 当前跳跃的最远边界intmax_length0;// 全局能到达的最远索引for(inti0;in;i){// 更新全局最远可达位置max_lengthmax(max_length,inums[i]);// 到达当前跳跃边界必须完成一次跳跃if(currenti){step;currentmax_length;}// 提前终止已能到达最后一个下标无需继续遍历if(currentn-
break;}returnstep;}};复杂度分析时间复杂度O ( n ) O(n)O(n)。
仅需遍历一次数组n为数组长度遍历过程中所有操作均为常数级空间复杂度O ( 1 ) O(
O(
。
仅使用step、current、max_length三个常数级变量无额外空间开销。