跳跃游戏 II | 贪心算法最优解（最少跳跃次数）

跳跃游戏 II | 贪心算法最优解（最少跳跃次数）

题目描述

给定一个长度为n的 0 索引整数数组nums，初始位置为数组下标 0。数组中每个元素nums[i]表示从下标i处可以向前跳跃的最大长度，即若处于索引i，可跳跃到任意满足i < j < n且j ≤ i + nums[i]的索引j。要求返回到达数组最后一个下标n-1的最小跳跃次数，题目保证一定可以到达最后一个下标。

核心特征分析

1. 数组类问题的算法选择优先级：贪心算法 > 动态规划（尤其当问题仅需“最优结果”而非“所有路径”时）；
2. 本题中“每个元素代表可跳跃的最大长度”是贪心算法的典型适配场景——无需记录所有跳跃路径，只需通过“局部最优选择”即可推导“全局最优解”（最少跳跃次数）。

算法选择与思路

算法选择

选择贪心算法作为最优解，核心原因如下：

• 动态规划需维护数组记录每个位置的最少步数，时间复杂度O ( n 2 ) O(n^2)O(n2)、空间复杂度O ( n ) O(n)O(n)，效率较低；
• 贪心算法仅需常数级变量记录关键状态，时间复杂度O ( n ) O(n)O(n)、空间复杂度O ( 1 ) O(1)O(1)，且能直接推导最少跳跃次数，是本题的最优解法。

贪心算法核心思路

关键变量定义

• step：记录已完成的跳跃次数；
• current：当前跳跃范围内能到达的最远边界（即本次跳跃的“终点”）；
• max_length：遍历过程中能到达的全局最远索引（所有可达位置中能跳的最远位置）。

算法执行步骤

1. 初始化step = 0、current = 0、max_length = 0（补充边界处理：若数组长度≤1，无需跳跃，直接返回0）；
2. 遍历数组中的每个索引i：
   • 刷新全局最远可达索引：max_length = max(max_length, i + nums[i])；
   • 若i == current（遍历到当前跳跃的边界），说明必须完成一次跳跃：
     ① 跳跃次数加1：step++；
     ② 更新下一次跳跃的边界：current = max_length；
   • 若current ≥ n-1（当前边界已覆盖最后一个下标），提前终止遍历（无需继续计算）；
3. 遍历结束后返回step。

完整解题代码

classSolution{public:intjump(vector<int>&nums){intn=nums.size();// 边界处理：数组长度≤1时，初始位置即为终点，无需跳跃if(n<=1)return0;intstep=0;// 最少跳跃次数intcurrent=0;// 当前跳跃的最远边界intmax_length=0;// 全局能到达的最远索引for(inti=0;i<n;i++){// 更新全局最远可达位置max_length=max(max_length,i+nums[i]);// 到达当前跳跃边界，必须完成一次跳跃if(current==i){step++;current=max_length;}// 提前终止：已能到达最后一个下标，无需继续遍历if(current>=n-1)break;}returnstep;}};

复杂度分析

• 时间复杂度：O ( n ) O(n)O(n)。仅需遍历一次数组，n为数组长度，遍历过程中所有操作均为常数级；
• 空间复杂度：O ( 1 ) O(1)O(1)。仅使用step、current、max_length三个常数级变量，无额外空间开销。

总结

1. 贪心算法解决“跳跃游戏 II”的核心是以“当前跳跃边界”为触发条件，每到边界就完成一次跳跃，并将下一次边界更新为全局最远可达位置；
2. 该解法通过“局部最优（每次跳最远）”实现“全局最优（最少次数）”，时间/空间复杂度均为最优；
3. 边界场景处理（如数组长度≤1）是保证代码健壮性的关键，需结合题目条件补充。