跳跃游戏（贪心算法）详解 | 时间O(n)空间O(1)最优解
在算法题中，跳跃游戏是经典的贪心算法应用场景，其核心需求是判断能否从数组第一个位置跳到最后一个位置，同时追求最优的时间和空间复杂度。本文将详细拆解贪心算法求解跳跃游戏的思路、逻辑细节、示例验证及复杂度分析，全程无代码，聚焦算法思想本身，适合新手理解和梳理笔记。
一、问题描述
给定一个非负整数数组 nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。
示例 1：
输入：nums = [2,3,1,1,4]输出：true解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
输入：nums = [3,2,1,0,4]输出：false解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
二、贪心算法核心思路
贪心算法的核心思想是「每一步都追求最优局部解，最终得到全局最优解」。对于跳跃游戏，我们的局部最优目标是：每遍历一个位置，就尽可能扩大当前能到达的最远范围，通过维护这个最远范围，判断是否能覆盖到数组末尾。
1. 核心变量定义
定义变量 mx，用于维护「当前所有可达位置中，能跳到的最远下标」。
初始值：mx = 0。因为初始时我们只能位于数组第一个下标（下标 0），此时最远能到达的位置就是自身，无任何跳跃动作。
2. 遍历逻辑拆解
从左到右逐个遍历数组的每个位置 i，遍历过程中执行两个关键操作：
判断当前位置是否可达：若 mx < i，说明即便用尽之前所有位置的跳跃能力，也无法到达当前位置 i，后续位置更无法触及，直接判定为「无法到达终点」，返回 false。
更新最远可达范围：若当前位置 i 可达（即 mx >= i），则站在位置 i 上，能跳跃的最远距离为 i + nums[i]（nums[i] 是位置 i 允许的最大跳跃步数）。将这个距离与当前的 mx 取最大值，更新 mx（即 mx = max(mx, i + nums[i])），实现「不断刷新最远可达边界」的目标。
3. 遍历结束判定
若能顺利遍历完整个数组（未在中途返回 false），说明所有位置都在可达范围内，且最终的 mx 必然覆盖数组的最后一个下标（否则遍历到最后一个位置时会触发 mx < i），因此直接返回 true。
三、示例推演
通过两个示例，一步步推演算法执行过程，直观感受逻辑流转。
示例 1：nums = [2,3,1,1,4]（可到达终点）
初始状态：mx = 0，准备遍历 i=0。
遍历i=0：mx=0 >= 0（可达），计算0+2=2，更新 mx = max(0,2) = 2。
遍历 i=1：mx=2 >= 1（可达），计算 1+3=4，更新 mx = max(2,4) = 4（此时已覆盖最后一个下标 4）。
遍历 i=2：mx=4 >= 2（可达），计算 2+1=3，3 < 4，mx 保持 4。
遍历 i=3：mx=4 >= 3（可达），计算 3+1=4，mx保持 4。
遍历 i=4：mx=4 >= 4（可达），计算 4+4=8，更新mx=8。
遍历结束，返回 true。
示例 2：nums = [3,2,1,0,4]（无法到达终点）
初始状态：mx = 0，准备遍历 i=0。
遍历 i=0：mx=0 >= 0（可达），计算 0+3=3，更新 mx=3。
遍历 i=1：mx=3 >= 1（可达），计算 1+2=3，mx 保持 3。
遍历 i=2：mx=3 >= 2（可达），计算 2+1=3，mx 保持 3。
遍历 i=3：mx=3 >= 3（可达），计算 3+0=3，mx 保持 3。
遍历i=4：mx=3 < 4（不可达），直接返回 false。
四、复杂度分析
1. 时间复杂度：O(n)
算法仅需从头到尾遍历一次数组，每个元素只被处理一次，遍历次数与数组长度 n 成正比，因此时间复杂度为线性阶 O(n)，是该问题的最优时间复杂度。
2. 空间复杂度：O(1)
仅使用了 mx、i 两个常数级变量，未开辟任何与数组规模相关的额外空间（如数组、哈希表等），因此空间复杂度为常数阶 O(1)，实现了空间最优。
五、算法核心总结
贪心策略体现：不纠结于「每一步跳多少步」，而是聚焦「每一步能到达的最远范围」，通过局部最优的范围扩张，实现全局是否可达的判断。
关键逻辑：mx 是算法的核心，始终维护当前可达的最远边界，遍历中仅需验证位置可达性并更新边界，逻辑简洁高效。
优势：相较于动态规划（时间 O(n²)、空间 O(n)），贪心算法在时间和空间上均有显著优化，是跳跃游戏问题的最优解法。
以上就是跳跃游戏贪心算法的完整解析，核心在于理解「最远可达边界」的维护逻辑。如果有疑问或其他延伸场景，欢迎在评论区交流～