跳跃游戏 II | 贪心算法最优解（最少跳跃次数）-平芜编程栈

跳跃游戏 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;}};