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

这是 LeetCode 45「跳跃游戏 II」的 Python3 实现采用贪心算法时间复杂度 O(n)空间复杂度 O(1)。classSolution:defjump(self,nums:List[int])-int:nlen(nums)ifn1:return0jumps0# 已使用的跳跃次数current_end0# 当前这步能到达的最远边界farthest0# 下一步能到达的最远边界foriinrange(n-1):# 不需要遍历最后一个元素# 更新下一步能到达的最远位置farthestmax(farthest,inums[i])# 到达当前步的边界时必须跳一步ificurrent_end:jumps1current_endfarthest# 提前退出如果已经能到达或超过终点ifcurrent_endn-1:breakreturnjumps核心思路贪心策略每一步都尽可能跳到最远但不急着跳而是先收集完当前步范围内的所有选择从中挑出下一步能跳最远的那个位置。双边界维护current_end当前这步第jumps步能覆盖到的最远下标。farthest在当前覆盖范围内再跳一步能到达的最远下标。触发跳跃当遍历指针i到达current_end时说明当前步的所有选择已考察完毕必须进行下一次跳跃并将边界扩展到farthest。示例验证输入: nums [2, 3, 1, 1, 4] i0: farthest max(0, 02) 2, i current_end(0) → jumps1, current_end2 i1: farthest max(2, 13) 4 i2: farthest max(4, 21) 3, i current_end(2) → jumps2, current_end4 (≥4, break) 输出: 2为什么遍历到n-2即可因为题目保证一定能到达终点当current_end n - 1时就已经能覆盖最后一个位置无需再处理最后一个元素本身。