跳跃游戏 | 贪心算法最优解（LeetCode经典题）

跳跃游戏 | 贪心算法最优解（LeetCode经典题）

题目描述

给定一个非负整数数组nums，你最初位于数组的第一个下标。数组中每个位置的元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达数组的最后一个下标，能则返回true，不能则返回false。

核心特征分析

1. 处理对象为数组类问题，这类问题通常可优先考虑动态规划或贪心算法解决；
2. 题目中“每个位置的元素代表能跳跃的最大长度”是贪心算法的典型应用特征——无需关注具体跳跃路径，只需聚焦“能到达的最远范围”即可验证可行性。

算法选择与思路

算法选择

本题仅需验证“能否到达最后一个下标”的可行性，无需罗列具体跳跃路径，因此选择贪心算法是最优解（相比动态规划，贪心算法时间复杂度相同且空间复杂度更低）。

贪心算法核心思路

1. 维护变量max_length，表示当前能到达的最大索引位置；
2. 遍历数组中的每个索引i：
   • 若当前索引i超过max_length，说明无法到达该位置，直接返回false；
   • 更新max_length为max(max_length, i + nums[i])（当前能到达的最远位置 = 历史最远位置 和 当前位置可跳最远位置 的较大值）；
   • 若max_length已≥数组最后一个索引，说明能到达终点，直接返回true；
3. 遍历结束后，兜底判断max_length是否≥数组最后一个索引（适配数组长度为1等边界场景）。

完整解题代码

classSolution{public:boolcanJump(vector<int>&nums){intn=nums.size();intmax_length=0;for(inti=0;i<n;i++){if(i>max_length)returnfalse;max_length=max(max_length,i+nums[i]);if(max_length>=n-1)returntrue;}returnmax_length>=n-1;}};

复杂度分析

• 时间复杂度：O(n)。仅需遍历一次数组，n为数组长度；
• 空间复杂度：O(1)。仅使用常数级额外空间（max_length、n、i三个变量）。

总结

1. 跳跃游戏可行性验证的核心是维护“能到达的最远索引”，贪心算法是该问题的最优解法；
2. 遍历中提前终止判断（无法到达当前索引/已确认能到终点时直接返回），可提升实际执行效率；
3. 该解法时间复杂度 O(n)、空间复杂度 O(1)，是本题的最优解。