【LeetCode 热题100】 45. 跳跃游戏 II 的算法思路及python代码

45. 跳跃游戏 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

算法思路

本文通过 贪心算法 解决最小跳跃次数问题，核心思想是在每一步尽可能跳到最远的位置，从而减少总跳跃次数。通过动态维护当前能到达的最远位置和当前跳跃边界，确保每次跳跃均为必要且最优。具体步骤如下：

算法步骤

1. 初始化变量：

   • maxPos：记录当前能到达的最远位置。
   • end：当前跳跃的边界，到达该边界时必须进行下一次跳跃。
   • step：记录跳跃次数。

2. 遍历数组：

   • 索引范围：遍历到 n-2（倒数第二个元素），因为到达末尾无需再跳。
   • 更新最远位置：对每个位置 i，若可达（i <= maxPos），更新 maxPos = max(maxPos, i + nums[i])。
   • 跳跃条件：当 i == end 时，表示已到达当前跳跃边界，需跳跃一次，更新 end = maxPos 并增加 step。

3. 返回结果：遍历结束后，step 即为最小跳跃次数。

切入点

• 贪心策略：每一步选择能跳到的最远位置，确保后续可选范围最大化。
• 跳跃边界控制：通过 end 标记当前跳跃的终点，到达时触发下一次跳跃。

关键点

• 动态维护最远位置：
  每次遍历时更新 maxPos，确保始终掌握当前所有可能跳跃中的最远可达位置。
• 跳跃时机的判断：
  当遍历到当前跳跃边界 end 时，必须进行下一次跳跃，并更新边界为新的 maxPos。
• 索引遍历范围优化：
  仅遍历到 n-2，因为到达最后一个元素无需跳跃。

复杂度分析

代码解析

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        maxPos, end, step = 0, 0, 0  # 初始化最远位置、跳跃边界、跳跃次数
        for i in range(n - 1):        # 遍历到倒数第二个元素即可
            if maxPos >= i:           # 确保当前位置可达
                maxPos = max(maxPos, i + nums[i])  # 更新当前能到达的最远位置
                if i == end:          # 到达当前跳跃边界，触发下一次跳跃
                    end = maxPos      # 更新跳跃边界为新的最远位置
                    step += 1         # 增加跳跃次数
        return step