LeetCode 45. Jump Game II 题解题目描述给定一个长度为n的0索引整数数组nums。初始位置为nums[0]。每个元素nums[i]表示从索引i向前跳转的最大长度。换句话说如果你在nums[i]处你可以跳转到任意nums[i j]处其中0 j nums[i]且i j n。返回到达nums[n - 1]的最小跳跃次数。生成的测试用例可以到达nums[n - 1]。示例 1输入nums [2,3,1,1,4] 输出2 解释跳到最后一个位置的最小跳跃数是 2。 从下标 0 跳到下标 1跳 1 步然后跳 3 步到达最后一个下标。示例 2输入nums [2,3,0,1,4] 输出2解题思路方法贪心算法思路维护三个变量current_end当前跳跃的结束位置farthest当前能够到达的最远位置jumps跳跃的次数遍历数组对于每个位置i更新farthest为max(farthest, i nums[i])如果i到达current_end说明需要进行一次跳跃增加jumps更新current_end为farthest如果current_end已经到达或超过最后一个下标结束遍历复杂度分析时间复杂度O(n)其中 n 是数组的长度。只需要遍历数组一次。空间复杂度O(1)只需要常数级的额外空间。代码实现方法贪心算法class Solution: def jump(self, nums: List[int]) - int: n len(nums) if n 1: return 0 current_end 0 farthest 0 jumps 0 for i in range(n - 1): # 更新能够到达的最远位置 farthest max(farthest, i nums[i]) # 如果到达当前跳跃的结束位置需要进行一次跳跃 if i current_end: jumps 1 current_end farthest # 如果已经能够到达最后一个下标提前结束 if current_end n - 1: break return jumps测试用例测试用例 1输入nums [2,3,1,1,4]输出2测试用例 2输入nums [2,3,0,1,4]输出2测试用例 3输入nums [1,2,3]输出2测试用例 4输入nums [1,1,1,1]输出3总结本题是贪心算法的经典问题主要考察对贪心思想的理解和应用。通过维护当前跳跃的结束位置和能够到达的最远位置我们可以高效地计算出到达最后一个下标所需的最小跳跃次数。贪心算法的核心思想是在每一步都做出当前情况下的最优选择从而希望最终得到全局最优解。在本题中我们的最优选择是在每一次跳跃中尽可能地覆盖更远的距离。这种方法不仅适用于跳跃游戏 II 问题还可以应用于许多其他需要贪心策略的问题例如加油站问题、分发饼干问题等。掌握贪心算法的思想对于解决这类问题非常重要。