跳跃游戏 II | 贪心算法最优解（最少跳跃次数）
题目描述
给定一个长度为n的 0 索引整数数组nums，初始位置为数组下标 0。数组中每个元素nums[i]表示从下标i处可以向前跳跃的最大长度，即若处于索引i，可跳跃到任意满足i < j < n且j ≤ i + nums[i]的索引j。要求返回到达数组最后一个下标n-1的最小跳跃次数，题目保证一定可以到达最后一个下标。
核心特征分析
- 数组类问题的算法选择优先级：贪心算法 > 动态规划（尤其当问题仅需“最优结果”而非“所有路径”时）；
- 本题中“每个元素代表可跳跃的最大长度”是贪心算法的典型适配场景——无需记录所有跳跃路径，只需通过“局部最优选择”即可推导“全局最优解”（最少跳跃次数）。
算法选择与思路
算法选择
选择贪心算法作为最优解，核心原因如下：
- 动态规划需维护数组记录每个位置的最少步数，时间复杂度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：遍历过程中能到达的全局最远索引（所有可达位置中能跳的最远位置）。
算法执行步骤
- 初始化
step = 0、current = 0、max_length = 0（补充边界处理：若数组长度≤1，无需跳跃，直接返回0）； - 遍历数组中的每个索引
i：- 刷新全局最远可达索引：
max_length = max(max_length, i + nums[i])； - 若
i == current（遍历到当前跳跃的边界），说明必须完成一次跳跃：
① 跳跃次数加1：step++；
② 更新下一次跳跃的边界：current = max_length； - 若
current ≥ n-1（当前边界已覆盖最后一个下标），提前终止遍历（无需继续计算）；
- 刷新全局最远可达索引：
- 遍历结束后返回
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三个常数级变量，无额外空间开销。
总结
- 贪心算法解决“跳跃游戏 II”的核心是以“当前跳跃边界”为触发条件，每到边界就完成一次跳跃，并将下一次边界更新为全局最远可达位置；
- 该解法通过“局部最优（每次跳最远）”实现“全局最优（最少次数）”，时间/空间复杂度均为最优；
- 边界场景处理（如数组长度≤1）是保证代码健壮性的关键，需结合题目条件补充。
