LeetCode 45. 跳跃游戏 II

题目描述
给定一个长度为 n 的非负整数数组 nums，初始位置在数组的第一个下标（索引 0）。数组中的每个元素表示在该位置可以跳跃的最大长度。例如 nums[i] = 3，表示从位置 i 最多可以向后跳 1、2 或 3 步。你的目标是使用最少的跳跃次数到达数组的最后一个下标（索引 n-1）。假设你总是可以到达数组末尾。

示例
输入：nums = [2,3,1,1,4]
输出：2
解释：从索引 0 跳 1 步到索引 1（可跳 3 步），再从索引 1 跳 3 步到末尾。

解题过程

1. 问题分析

• 核心问题：在保证可达的前提下，最小化跳跃次数。
• 关键观察：每次跳跃时，应选择能让你跳得最远的方案（贪心思想）。
• 注意：不能简单每一步都选当前能跳最远的位置，而是要在当前可跳范围内，选择下一步能覆盖最远距离的位置。

2. 算法思路（贪心策略）
定义三个变量：

• jumps：记录当前已跳次数。
• current_end：当前跳跃能到达的最远边界（初始为 0）。
• farthest：在当前可跳范围内，能到达的最远位置。

遍历数组（不访问最后一个元素，因为到达终点后无需再跳）：

1. 更新 farthest 为 max(farthest, i + nums[i])。
2. 当遍历到 current_end 时，说明已完成当前跳跃，必须进行下一次跳跃：
   • jumps += 1
   • current_end = farthest（更新为下一步能到达的最远边界）
3. 若 farthest 已覆盖终点，提前终止。

3. 逐步推演示例
数组：[2, 3, 1, 1, 4]
初始化：jumps = 0, current_end = 0, farthest = 0

• 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 保持 4
  • 此时 i == current_end (2)，需跳跃：jumps = 2，current_end = 4
  • 由于 current_end ≥ 4（终点索引），结束。

结果：jumps = 2。

4. 为什么这是最优解？

• 每次跳跃都选择下一步能覆盖最远距离的方案，保证了后续选择的可能性最大。
• 通过 current_end 分割跳跃区间，确保每次跳跃都是必要的（贪心选择性）。

5. 代码实现（Python）

def jump(nums):
    jumps = 0
    current_end = 0
    farthest = 0
    for i in range(len(nums) - 1):  # 不访问最后一个元素
        farthest = max(farthest, i + nums[i])
        if i == current_end:
            jumps += 1
            current_end = farthest
            if farthest >= len(nums) - 1:
                break
    return jumps

复杂度分析

• 时间复杂度：O(n)，只需遍历一次数组。
• 空间复杂度：O(1)，仅使用常数变量。