摘要
在算法设计领域，数组跳跃可达性问题是一类经典的贪心算法应用场景。本文针对 “给定非负整数数组，判断从第一个下标出发能否到达最后一个下标” 这一问题，深入剖析了贪心算法的核心思想与实现逻辑。通过对算法的时间复杂度、空间复杂度分析，结合具体示例验证，并与其他潜在解法对比，证明了该贪心算法在效率与简洁性上的显著优势。实验结果表明，该算法能够在 O (n) 时间复杂度和 O (1) 空间复杂度内，高效解决长度不超过 10⁴的数组跳跃可达性判断问题，为同类问题的求解提供了可靠参考。
关键词
贪心算法；数组；跳跃可达性；时间复杂度；空间复杂度
一、问题背景与意义
1.1 问题描述
给定一个非负整数数组nums，数组的每个元素nums[i]表示在下标i位置可以跳跃的最大长度。初始状态下，我们位于数组的第一个下标（即下标 0），需要判断是否能够通过一系列跳跃操作到达数组的最后一个下标（即下标n-1，其中n为数组长度）。若能到达，返回true；否则，返回false。
1.2 问题约束
根据题目要求，数组存在以下约束条件：
- 数组长度1 ≤ nums.length ≤ 10⁴，这意味着算法需要具备一定的效率，以应对较大规模的输入；
- 数组元素0 ≤ nums[i] ≤ 10⁵，元素的非负性是问题的重要前提，同时较大的元素值也对算法的稳定性提出了要求。
1.3 问题意义
该问题广泛存在于路径规划、游戏设计等实际场景中。例如，在游戏地图中，角色需要从起点通过有限的跳跃步数到达终点，每个位置的跳跃能力有限，此时就需要快速判断角色是否能够成功抵达终点。此外，该问题也是算法学习中的经典案例，能够很好地体现贪心算法 “局部最优导向全局最优” 的核心思想，对于理解贪心策略的适用场景与实现逻辑具有重要意义。
二、算法选择与分析
2.1 潜在解法对比
针对数组跳跃可达性问题，常见的潜在解法包括暴力回溯法、动态规划法与贪心算法，三者的对比分析如下：
- 暴力回溯法：通过枚举所有可能的跳跃路径，判断是否存在到达最后一个下标的路径。该方法的时间复杂度为 O (2ⁿ)，随着数组长度的增加，计算量呈指数级增长，无法满足n=10⁴的规模要求，实际应用中几乎不可行。
- 动态规划法：定义dp[i]表示是否能够到达下标i，通过遍历数组，更新dp数组的值。该方法的时间复杂度为 O (n²)，空间复杂度为 O (n)，虽然相比暴力回溯法有显著提升，但对于n=10⁴的数组，仍会产生较大的计算开销，效率有待优化。
- 贪心算法：通过维护一个 “最远可达距离” 变量，在遍历数组的过程中不断更新该变量，若最远可达距离能够覆盖最后一个下标，则返回true。该方法的时间复杂度仅为 O (n)，空间复杂度为 O (1)，在效率与空间占用上均表现最优，完全满足题目约束条件，因此成为本问题的最优解法。
2.2 贪心算法的适用性
贪心算法的核心思想是在每一步选择中都采取当前状态下的最优决策，即 “局部最优”，从而希望最终能够达成 “全局最优”。在数组跳跃可达性问题中，“局部最优” 表现为在当前可到达的范围内，选择能够跳得最远的位置，通过不断扩大 “最远可达距离”，最终判断该距离是否能够覆盖最后一个下标。这种策略之所以有效，是因为如果存在一条从起点到终点的路径，那么通过维护 “最远可达距离”，必然能够在遍历过程中覆盖这条路径上的所有节点，进而到达终点；反之，若 “最远可达距离” 始终无法覆盖终点，则必然不存在这样的路径。因此，贪心算法在本问题中具有明确的适用性。
三、贪心算法详细实现
3.1 算法原理
算法的核心在于维护一个变量max_reach，用于记录当前能够到达的最远下标。具体原理如下：
- 初始化max_reach为 0，代表初始状态下（位于下标 0）能够到达的最远下标为 0；
- 遍历数组的每个下标i：
- 若当前下标i超过了max_reach，说明当前下标无法通过之前的跳跃到达，后续下标更无法到达，直接返回false；
- 否则，更新max_reach为max(max_reach, i + nums[i])，其中i + nums[i]表示从当前下标i出发能够到达的最远下标，通过取最大值，确保max_reach始终是当前可到达的最远范围；
- 若在遍历过程中，max_reach已经大于等于数组的最后一个下标（n-1），说明已经能够到达终点，直接返回true；
- 若遍历结束后仍未返回false，则说明能够到达终点，返回true。
3.2 代码实现
根据上述算法原理，使用 C++ 语言实现的代码如下：
#include <vector> #include <algorithm> // 用于max函数 using namespace std; class Solution { public: bool canJump(vector<int>& nums) { int n = nums.size(); // 获取数组长度 int max_reach = 0; // 初始化最远可达距离为0 for (int i = 0; i < n; i++) { // 若当前下标超过最远可达距离，无法继续前进，返回false if (i > max_reach) { return false; } // 更新最远可达距离：取当前最远可达距离与从当前下标出发的最远距离的最大值 max_reach = max(max_reach, i + nums[i]); // 若最远可达距离已覆盖最后一个下标，直接返回true if (max_reach >= n - 1) { return true; } } // 遍历结束后，说明能够到达终点，返回true return true; } };3.3 代码解释
- 数组长度获取：通过nums.size()获取数组nums的长度n，为后续遍历与终点判断提供依据；
- 最远可达距离初始化：max_reach = 0，初始状态下只能到达下标 0，符合实际情况；
- 遍历数组：通过for循环遍历数组的每个下标i：
- 不可达判断：if (i > max_reach)，若当前下标i不在可到达范围内，说明后续下标更无法到达，直接返回false，提前终止程序，减少不必要的计算；
- 更新最远可达距离：max_reach = max(max_reach, i + nums[i])，确保max_reach始终是当前状态下能够到达的最远下标，体现了 “局部最优” 的选择；
- 提前返回成功：if (max_reach >= n - 1)，若最远可达距离已覆盖终点，说明无需继续遍历，直接返回true，进一步优化效率；
- 遍历结束返回：若循环正常结束，说明在遍历过程中未出现 “不可达” 的情况，且最终max_reach必然覆盖终点（否则会在遍历中返回false），因此返回true。
四、示例验证与分析
为了验证算法的正确性，本文结合题目给出的两个示例进行详细分析。
4.1 示例 1：可到达终点
输入：nums = [2, 3, 1, 1, 4]
预期输出：true
遍历过程分析：
- 初始状态：n = 5，max_reach = 0；
- 遍历i = 0：
- i = 0 ≤ max_reach = 0，可达；
- 更新max_reach = max(0, 0 + 2) = 2；
- `max_reach = 2 下标为 4），继续遍历；
- 遍历i = 1：
- i = 1 ≤ max_reach = 2，可达；
- 更新max_reach = max(2, 1 + 3) = 4；
- max_reach = 4 ≥ 4，已覆盖终点，返回true。
结果分析：
从遍历过程可见，在遍历到下标 1 时，最远可达距离已覆盖终点下标 4，算法提前返回true，与预期结果一致。实际跳跃路径可参考题目解释（从下标 0 跳 1 步到下标 1，再从下标 1 跳 3 步到下标 4），验证了算法的正确性。
4.2 示例 2：不可到达终点
输入：nums = [3, 2, 1, 0, 4]
预期输出：false
遍历过程分析：
- 初始状态：n = 5，max_reach = 0；
- 遍历i = 0：
- i = 0 ≤ max_reach = 0，可达；
- 更新max_reach = max(0, 0 + 3) = 3；
- `max_reach = 3 继续遍历；
- 遍历i = 1：
- i = 1 ≤ max_reach = 3，可达；
- 更新max_reach = max(3, 1 + 2) = 3；
- `max_reach = 3 继续遍历；
- 遍历i = 2：
- i = 2 ≤ max_reach = 3，可达；
- 更新max_reach = max(3, 2 + 1) = 3；
- `max_reach = 3 继续遍历；
- 遍历i = 3：
- i = 3 ≤ max_reach = 3，可达；
- 更新max_reach = max(3, 3 + 0) = 3；
- `max_reach = 3 继续遍历；
- 遍历i = 4：
- i = 4 > max_reach = 3，不可达，返回false。
结果分析：
遍历到下标 4 时，当前下标超过了最远可达距离 3，说明无法到达下标 4，算法返回false，与预期结果一致。该示例验证了算法在 “存在不可达下标” 场景下的正确性，即当最远可达距离无法继续扩大且未覆盖终点时，能够准确判断为不可达。
五、复杂度分析
5.1 时间复杂度
算法通过一次for循环遍历数组，循环执行次数等于数组的长度n，每次循环内部的操作（判断、取最大值、赋值）均为常数时间操作（O (1)）。因此，算法的时间复杂度为O(n)，其中n为数组的长度。该时间复杂度能够高效应对n=10⁴的规模要求，在实际应用中表现优异。
5.2 空间复杂度
算法在执行过程中，仅使用了有限的几个变量（n、max_reach、i），这些变量的空间占用与数组长度n无关，始终为常数级别。因此，算法的空间复杂度为O(1)，属于最优的空间复杂度，能够有效节省内存资源，尤其在处理大规模数组时优势明显。
六、算法优化与拓展
6.1 算法优化点
本文实现的贪心算法已具备较高的效率，但仍可从以下细节进行优化：
- 提前终止遍历：在遍历过程中，一旦max_reach覆盖终点下标，立即返回true，避免后续不必要的遍历，如示例 1 中仅遍历到下标 1 就提前返回，进一步减少了计算量；
- 避免冗余计算：在更新max_reach时，仅需比较当前max_reach与i + nums[i]，无需考虑其他冗余信息，确保每次更新操作的高效性。
6.2 问题拓展
基于本问题的贪心算法思想，可拓展解决以下类似问题：
- 跳跃游戏 II：在 “能够到达终点” 的前提下，求到达终点所需的最少跳跃次数。该问题同样可使用贪心算法，通过维护 “当前跳跃的最远边界” 与 “下一次跳跃的最远边界”，实现最少跳跃次数的计算；
- 跳跃游戏 III：给定数组，判断是否能够从起点出发，跳跃到值为 0 的下标。该问题可结合广度优先搜索（BFS）或深度优先搜索（DFS），但贪心思想仍可用于优化搜索过程，优先选择跳跃范围更大的路径，减少搜索次数。
七、结论
7.1 结论
本文针对非负整数数组跳跃可达性问题，提出了基于贪心算法的解决方案。通过理论分析与示例验证，得出以下结论：
- 贪心算法在本问题中具有显著的效率优势，时间复杂度为 O (n)，空间复杂度为 O (1)，能够高效应对题目约束的数组规模；
- 算法通过维护 “最远可达距离”，实现了 “局部最优导向全局最优”，能够准确判断是否能够到达数组的最后一个下标；
- 与暴力回溯法、动态规划法相比，贪心算法在效率与空间占用上均表现最优，是本问题的最优解法。
参考文献
[1] 算法导论（原书第 3 版）. Thomas H. Cormen 等。机械工业出版社.
[2] 编程珠玑（第 2 版）. Jon Bentley. 人民邮电出版社.
[3] LeetCode 官方题解。跳跃游戏（题号：55）. https://leetcode-cn.com/problems/jump-game/solution/tiao-yue-you-xi-by-leetcode-solution/
