Kimi LeetCode 45. 跳跃游戏 II Python3实现

这是 LeetCode 45「跳跃游戏 II」的 Python3 实现，采用贪心算法，时间复杂度 O(n)，空间复杂度 O(1)。

classSolution:defjump(self,nums:List[int])->int:n=len(nums)ifn==1:return0jumps=0# 已使用的跳跃次数current_end=0# 当前这步能到达的最远边界farthest=0# 下一步能到达的最远边界foriinrange(n-1):# 不需要遍历最后一个元素# 更新下一步能到达的最远位置farthest=max(farthest,i+nums[i])# 到达当前步的边界时，必须跳一步ifi==current_end:jumps+=1current_end=farthest# 提前退出：如果已经能到达或超过终点ifcurrent_end>=n-1:breakreturnjumps

核心思路

1. 贪心策略：每一步都尽可能跳到最远，但不急着跳，而是先收集完当前步范围内的所有选择，从中挑出下一步能跳最远的那个位置。
2. 双边界维护：
   • current_end：当前这步（第jumps步）能覆盖到的最远下标。
   • farthest：在当前覆盖范围内，再跳一步能到达的最远下标。
3. 触发跳跃：当遍历指针i到达current_end时，说明当前步的所有选择已考察完毕，必须进行下一次跳跃，并将边界扩展到farthest。

示例验证

输入: nums = [2, 3, 1, 1, 4] i=0: farthest = max(0, 0+2) = 2, i == current_end(0) → jumps=1, current_end=2 i=1: farthest = max(2, 1+3) = 4 i=2: farthest = max(4, 2+1) = 3, i == current_end(2) → jumps=2, current_end=4 (≥4, break) 输出: 2

为什么遍历到n-2即可？

因为题目保证一定能到达终点，当current_end >= n - 1时就已经能覆盖最后一个位置，无需再处理最后一个元素本身。