前言

本专栏文章为《LeetCode 热题 100》的刷题题解，相关内容如有侵权，立即删除。

一、题目

1、原题链接

45.跳跃游戏 II

2、题目描述

二、个人思路整理

1、思路分析

核心思路：题目要求用最少跳跃次数到达数组末尾，且保证一定可达。不需要枚举具体跳到哪一个格子上，而是维护当前跳跃步数所能覆盖的边界：

1. 维护两个指针/边界：

   • cur_end：当前这一步最远能到达的边界。
   • farthest：在当前步数能覆盖的所有位置中起跳，下一步最多能触达的最远位置（max(farthest, i + nums[i])）。

2. 什么时候增加跳跃次数：

   • 遍历数组索引 $i$。
   • 当 $i$ 遍历到了 cur_end（即当前这一步能覆盖的极限），说明必须进行下一次跳跃了：
     • step++
     • 更新当前边界 cur_end = farthest

3. 遍历终止条件：遍历到 nums.length - 2 即可（即 $i<n-1$），不需要遍历最后一个元素。因为如果遍历到 $n-1$，且恰好 $i==cur\_end$，会导致无故多加一次跳跃步数；而在 $n-2$ 之前触发更新后，farthest 必然已经 $\ge n-1$。

2、解题代码

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        // 数组长度为 1 时，初始就在终点，无需跳跃
        if (n <= 1) {
            return 0;
        }

        int steps = 0;     // 记录最少跳跃次数
        int cur_end = 0;   // 当前这一步跳跃所能覆盖的最远右边界
        int farthest = 0;  // 从当前步内任意位置起跳，下一步能触达的最远位置

        // 注意：遍历到 n - 2 即可，不需要遍历最后一个位置
        // 因为当到达 n - 2 时，cur_end 已经被更新为覆盖或超过终点 (n - 1) 的位置
        for (int i = 0; i < n - 1; i++) {
            // 实时维护在当前覆盖范围内起跳能达到的最远距离
            farthest = max(farthest, i + nums[i]);

            // 遍历到了当前步的边界，说明必须迈出下一次跳跃
            if (i == cur_end) {
                steps++;       // 步数增加
                cur_end = farthest;  // 将边界更新为之前计算出的最远可达位置
            }
        } 

        return steps;
    }
};

复杂度分析

• 时间复杂度：$O(n)$，只需单次遍历数组。
• 空间复杂度：$O(1)$，仅需常数级别的变量维护边界。

三、知识风暴

贪心算法（Greedy Algorithm） 是本题的核心算法思想。它通过在每一步做出当前看起来最优的选择，期望最终得到全局最优解。对于「跳跃游戏 II」这类具有最优子结构性质的问题，贪心策略往往能以 $O(n)$ 的复杂度高效求解。

算法核心思想：

• 局部最优推导全局最优：每一步都选择「能跳到最远位置」的起跳点，从而用最少的步数覆盖整个数组。本题中，维护当前步数能覆盖的边界 cur_end，当遍历到边界时再迈出下一步，即可保证步数最少。
• 无需回溯：贪心算法不回溯、不枚举所有可能路径，只关注当前可达范围内的最远位置，因此时间复杂度仅为 $O(n)$。
• 与动态规划的区别：动态规划需要记录每个位置的最少步数并逐一比较；而贪心只维护「当前步的边界」和「下一步的最远位置」两个变量，空间复杂度降为 $O(1)$。

常见对比：贪心 vs 动态规划

• 贪心算法：时间复杂度 $O(n)$，空间复杂度 $O(1)$。适合每一步的局部最优能直接推导全局最优的场景，代码简洁高效。
• 动态规划：时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。适合需要枚举所有子问题、且局部最优不能直接决定全局最优的场景，通用性更强但开销更大。
• 共同点：两者都依赖「最优子结构」性质。区别在于贪心只保留一个当前最优状态，而动态规划需要维护一张状态表。

贪心算法的设计思想：

• 核心思想：在遍历过程中，始终维护「当前这一步能到达的最远边界」和「从当前边界内任意位置起跳能到达的更远位置」。当遍历到当前边界时，步数加一，并将边界更新为更远位置。
• 与本题的联系：跳跃游戏 II 保证一定可达，因此贪心策略不会出现「跳不到终点」的失败情况。我们只需在到达终点前不断扩展边界，即可得到最少步数。
• 注意事项：贪心算法并不总是正确，需要先证明「局部最优能推出全局最优」。本题中，每一步都跳到最远位置不会比跳到较近位置更差，因此贪心成立。

使用要点：

• 边界变量：cur_end 记录当前步数能覆盖的最远下标，farthest 记录从当前覆盖范围内起跳能到达的更远下标。
• 更新时机：遍历到 cur_end 时步数加一，并将 cur_end 更新为 farthest，表示进入下一跳。
• 遍历范围：只需遍历到 n - 2，避免在终点处多算一步。
• 结果返回：遍历结束后 steps 即为最少跳跃次数。

算法变体与扩展：

• 跳跃游戏 I（LeetCode 55）：只判断能否到达终点，是本题的简化版，同样可用贪心维护最远可达位置。
• 跳跃游戏 III（LeetCode 1306）：从起点出发，每次可向左或向右跳 nums[i] 步，判断能否到达值为 0 的位置，需用 BFS/DFS 而非贪心。
• 加油站（LeetCode 134）：环形路径上的贪心问题，判断能否绕行一圈并找到起点。
• 分发糖果（LeetCode 135）：两次遍历的贪心策略，分别处理左、右相邻关系。

相关 LeetCode 例题：

• 55. 跳跃游戏（贪心 + 最远可达位置）
• 134. 加油站（贪心 + 环形路径）
• 135. 分发糖果（贪心 + 两次遍历）
• 45. 跳跃游戏 II（本题，贪心 + 最少步数）