hot100 跳跃游戏(55)

本题采用贪心算法又称“最远可达边界单调扫描法”解决一维数组可达性判定问题。其核心本质是将原本属于图论连通性或动态规划的状态空间搜索简化为在单次线性扫描中动态维护与收敛全局最远可达下标边界mx。当前提供的源码实现了在时间复杂度 O(n) 和额外空间复杂度 O(1) 条件下的全局最优检索最终走向是精准判定初始位置能否跨越所有零值障碍并覆盖最后一个数组下标。一、 问题本质与数据模型对于给定的非负整数数组nums其下标对应着一维物理空间中的连续格子格子内存储的数值代表从当前位置出发能够向右跨越的最大步长。题目要求的本质是判断是否存在一条从起始下标0到终止下标nums.length - 1的有效连续跳跃路径。这一问题在数据建模上可以从三个不同的抽象视角进行解析1. 图论视角有向无环图DAG的可达性分析若将每个数组下标i视为图中的节点 $v_i$从下标i向右延伸的每一步跳跃相当于建立了一条有向边E { (i, j) | i j i nums[i] }整个数组构成了一个规模为n的有向无环图DAG。求解是否能到达最后一个下标等价于求解从源点v_0出发是否存在一条能够到达汇点v_{n-1}的有向路径。由于每个节点向外辐射的边数可以多达nums[i]条全图的边数规模可达O(n^2)。2. 动态规划视角区间重叠与状态转移设状态dp[i]表示是否能够从起点0到达下标i。状态转移方程可以表示为dp[i] true当且仅当存在某个j i使得dp[j] true且j nums[j] i。这种状态建模要求对每一个位置i向左回溯检查所有可能的前驱节点j导致算法的时间开销退化至O(n^2)。3. 贪心视角连续可达区间的右边界扩展观察发现如果一个位置x是可达的那么从起点到x之间的所有位置也必然都是可达的。因此可达集合在物理空间上始终表现为一段连续的闭区间[0, mx]。起点边界初始时刻位于下标0故初始可达区间为[0, nums[0]]即mx nums[0]。边界演进当指针i从0开始向右推进时只要i处于当前可达区间[0, mx]内部即满足i mx那么位置i本身就是可达的。增量更新位于位置i时从该点能到达的最远位置为i nums[i]。因此全局最远可达边界可以被更新为mx max(mx, i nums[i])。通过将对离散路径的搜索抽象为对连续区间右端点mx的单调扩展问题被转化为一个仅需维护单一标量mx的线性扫描过程。二、 算法演进对比在解决跳跃游戏这一经典可达性判定问题时不同算法在时空开销及计算模型上存在显著演进路线解法名称时间复杂度空间复杂度核心原理物理瓶颈 / 缺陷回溯搜索法DFS / BFSO(2^n)O(n)递归尝试当前位置允许的所有跳跃步长穷举所有分支存在海量重复子路径计算面对平坦数组如全 1时引发指数级爆栈自顶向下记忆化搜索O(n^2)O(n)在 DFS 基础上引入memo数组记录已验证不可达的下标需要额外的数组开销与递归栈消耗仍需二次循环回溯状态自底向上动态规划DPO(n^2)O(n)维护boolean dp[]数组对每个位置回溯核验前驱节点无法利用可达区间的连续性特征进行了大量无意义的前驱扫描贪心最远边界法当前解法O(n)O(1)维护单调递增的右边界mx一次线性扫描完成判决仅需要一个标量无需任何额外内存开销耗时严格收敛于线性阶三、 核心分支控制逻辑与数学证明当前源码的控制流极为精简仅包含一个for循环与两个核心判断语句。其逻辑架构如下class Solution { public boolean canJump(int[] nums) { int mx 0; for (int i 0; i nums.length; i) { if (i mx) { return false; } mx Math.max(mx, nums[i] i); } return true; } }其内部决策逻辑证明如下1. 阻断分支if (i mx)执行直接返回false。数学证明反证法设当前循环指针推进到了索引i但条件i mx成立。由于mx代表了从起点0出发经过前面所有可能路径所能到达的最大物理索引。若i mx说明前方所有可达位置所能提供的最强跳跃力都无法延伸至当前位置i。根据空间连续性定理由于位置i无法到达任何大于i的后续位置j (j i)也绝不可能从i或i之前的节点到达。因此整个数组的可达链条在此处发生物理断裂后续搜索无须继续直接判定全局不可达。2. 状态递推分支mx Math.max(mx, nums[i] i)执行取当前边界mx与当前节点可达最远距离nums[i] i的较大者更新mx。数学证明数学归纳法基础步骤当i 0时起点必然可达。从起点出发最远可达0 nums[0]公式给出mx max(0, nums[0]) nums[0]命题成立。归纳假设假设当遍历至i k (k n - 1)且未触发k mx时mx精确记录了区间[0, k]内所有节点所能辐射的最右端点。归纳递推当指针推进到i k 1时因k 1 mx故位置k 1必然可达。从k 1出发能到达的最右端点为(k 1) nums[k 1]。则区间[0, k 1]内所有节点能辐射的最右端点为max( 集合 [0, k] 的最右端点, (k 1) nums[k 1] )即max(mx, nums[k 1] (k 1))。命题对i k 1依然成立。由此证明了该递推式在全流程中的无损正确性。四、 算法执行状态机步进示例为了直观展现算法在不同输入矩阵下的内部状态变迁下面分别对成功匹配示例与阻断失败示例进行状态机跟踪。示例 1成功抵达轨迹nums [2, 3, 1, 1, 4]数组长度n 5目标为到达下标4。步骤指针 i当前值 nums[i]理论辐射点 nums[i] i检查 i mx最远边界 mx 更新逻辑状态机判定结论初始----mx 0准备遍历1020 2 20 0(False)mx max(0, 2) 2位置0可达边界扩张至22131 3 41 2(False)mx max(2, 4) 4位置1可达边界扩张至43212 1 32 4(False)mx max(4, 3) 4位置2可达边界保持为44313 1 43 4(False)mx max(4, 4) 4位置3可达边界保持为45444 4 84 4(False)mx max(4, 8) 8位置4可达到达终点终止-----循环正常结束返回true在第 1 步遍历到下标1时mx就已经成功扩展到了4即最后一个下标。后续遍历安全通过最终返回true。示例 2障碍阻断轨迹nums [3, 2, 1, 0, 4]数组长度n 5目标为到达下标4。步骤指针 i当前值 nums[i]理论辐射点 nums[i] i检查 i mx最远边界 mx 更新逻辑状态机判定结论初始----mx 0准备遍历1030 3 30 0(False)mx max(0, 3) 3位置0可达边界扩张至32121 2 31 3(False)mx max(3, 3) 3位置1可达边界保持为33212 1 32 3(False)mx max(3, 3) 3位置2可达边界保持为34303 0 33 3(False)mx max(3, 3) 3位置3可达但此处数值为 0544-4 3(True)触发阻断指针突破边界返回false在步骤 4 处理下标3时由于其值为0无法贡献任何额外的跳跃增量导致mx停滞在3。当指针推进到下标4时触发4 3条件算法立即拦截并返回false。五、 源码实现与工程细节以下为带工程级详细注释的 Java 源代码实现class Solution { /** * 判断是否能到达二叉树/数组的最后一个下标 * * param nums 非负整数数组每个元素代表在该位置可以跳跃的最大长度 * return 若能到达最后一个下标返回 true否则返回 false */ public boolean canJump(int[] nums) { // 边界保护若数组为空直接判定不可达 if (nums null || nums.length 0) { return false; } // mx 变量用于记录当前所能到达的最远物理下标位置初始值定位在起点 0 int mx 0; int n nums.length; // 线性扫描数组中的每一个格点 for (int i 0; i n; i) { // 安全防护网若当前指针 i 超过了此前能扩展的最远边界 mx // 说明当前位置无法从起点通过任何路径到达发生断层直接返回 false if (i mx) { return false; } // 动态更新最远可达边界 // 取“原有最远边界”与“从当前位置 i 出发能跳到的最远位置 (i nums[i])”的最大值 mx Math.max(mx, nums[i] i); // 性能优化剪枝一旦最远边界已经覆盖或超越了最后一个下标即可提前终止循环 if (mx n - 1) { return true; } } // 若完成全盘扫描均未发生中断说明最后一个下标安全可达 return true; } }代码逻辑优化点说明原版代码中for循环会完整遍历整个数组。在实际工程落地时可以加入一行剪枝逻辑Javaif (mx n - 1) { return true; }当mx的数值增长到大于或等于n - 1时意味着最后一个下标已经被纳入可达区间此时无需继续后向遍历剩余的元素直接提前返回true可节省后续不必要的循环核验消耗。六、 复杂度分析1. 时间复杂度O(n)最坏情况分析算法包含一个针对数组nums的单层for循环。在最坏情况下例如数组每个元素均为1或者最远边界直到最后才覆盖终点循环体将精准执行n次。常数阶操作在每一次循环内部仅执行了一次整型数值比较i mx一次加法运算nums[i] i以及一次最值取值Math.max。这些操作均由 CPU 的算术逻辑单元ALU在常数时间O(1)内完成。提前终止引入mx n - 1剪枝后平均遍历次数将显著低于n。例如对于nums [10, 1, 1, 1, ...]算法在第 1 次迭代完成后即可直接退出。结论整体时间复杂度与数组长度n呈严格的线性正比关系表示为O(n)。2. 空间复杂度O(1)内存分配分析算法在执行过程中仅申请了mx和n两个基础数据类型int的局部变量用作物理坐标与边界的定位控制。无动态扩容未开辟任何与输入规模n相关的外部引用、辅助数组或数据结构未触发任何隐式或显式的堆内存申请。调用栈开销算法采用纯粹的迭代结构函数调用栈深度为常数阶O(1)。结论额外空间复杂度恒定为O(1)。七、 工业边界处理与算法延伸1. 极端边界测试用例在实际工程应用与自动化测试UT场景中该算法面临以下几种典型边界情况的考验单元素数组(nums [0])行为n 1循环在i 0时mx max(0, 0 0) 0。触发mx n - 1(即0 0)直接返回true。结论起点即终点逻辑完备。首元素为零多元素数组(nums [0, 2, 3])行为i 0时mx 0。推进到i 1时触发1 0判定直接返回false。结论困在起点正确拦截。数值溢出隐患防护隐患若nums[i]与i均为极大的正整数nums[i] i可能发生 32 位有符号整型算术溢出Integer Overflow变为负数。防护由于题目提示n 10^4且nums[i] 10^5i nums[i]的最大理论值为10^4 10^5 110000远低于Integer.MAX_VALUE(即2147483647)因此直接相加不会引发数值溢出。2. 算法变体延伸跳跃游戏 II最少跳跃次数跳跃游戏Jump Game存在一个经典的延伸问题——跳跃游戏 IILeetCode 45假设你总是可以到达数组的最后一个位置要求返回到达最后一个下标的最小跳跃次数。这一变体同样可以通过贪心算法解决但需要将单一的最远边界拆解为“当前步长能达到的最远边界”与“下一步能达到的最远边界”Javaclass Solution { public int jump(int[] nums) { int steps 0; // 记录跳跃步数 int end 0; // 当前这一步所能到达的最远边界 int maxPos 0; // 下一步所能到达的最远边界 // 注意遍历到 n - 1 即可因为在 n - 1 处不需要再进行跳跃 for (int i 0; i nums.length - 1; i) { maxPos Math.max(maxPos, i nums[i]); // 当到达了当前这一步的边界时必须强制发起下一次跳跃 if (i end) { end maxPos; // 更新边界为下一步的最远位置 steps; // 步数自增 } } return steps; } }从“判断可达性”到“求解最小跳跃步数”贪心的核心思想依然高度统一不关注具体跳到了哪一个节点而是关注每一步能拓宽的最大物理边界。通过维持边界的单调性成功将原本复杂的组合优化问题降维至线性时间复杂度。