LeetCodehot 力扣热题100 跳跃游戏2

题目解析

我们需要从数组 nums 的起始位置 0 处，跳跃到数组的最后一个位置，并求最小跳跃次数。其中，nums[i] 表示在索引 i 处最多可以向前跳的步数。

示例：

vector<int> nums = {2, 3, 1, 1, 4};

目标是从索引 0 跳到索引 4，最少跳跃次数是 2（0 → 1 → 4）。

解法：贪心 + 层次遍历（BFS）

思路

这道题可以通过贪心策略求解：

1. 维护 maxReach 变量，表示在当前层范围内，能跳到的最远索引。

2. 维护 end 变量，表示当前层的跳跃边界。当遍历到 end 时，必须执行一次跳跃。

3. 每次跳跃时，更新 end = maxReach，表示当前层的最远可达范围。

4. 当 end 超过或等于终点时，跳出循环。

为什么可以用贪心？

• 每次跳跃选择在当前范围内能跳得最远的点，保证最少步数。

代码

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return 0; // 只有一个元素，直接在终点

        int maxReach = 0;  // 当前可到达的最远位置
        int end = 0;       // 当前跳跃的边界
        int steps = 0;     // 记录跳跃次数

        for (int i = 0; i < n - 1; i++) {
            maxReach = max(maxReach, i + nums[i]); // 计算当前范围内最远能到达的索引

            if (i == end) { // 当前层的范围走完了，需要跳跃
                steps++;
                end = maxReach; // 更新下一次跳跃的边界
                if (end >= n - 1) break; // 如果下一次跳跃能到终点，则跳出循环
            }
        }
        return steps;
    }
};

运行步骤

以 nums = {2, 3, 1, 1, 4} 为例，分析代码执行过程：

变量初始化

int maxReach = 0;  // 记录当前层内最远可到达的索引
int end = 0;       // 记录当前跳跃的边界
int steps = 0;     // 记录跳跃次数

遍历数组

最终返回 steps = 2。

时间复杂度分析

• 代码只遍历了一遍数组，没有额外的嵌套循环。

• 每个元素最多只被访问一次，因此时间复杂度是 O(n)。

空间复杂度

• 只用了几个整型变量，没有额外的数组或数据结构，空间复杂度是 O(1)。

总结