📝 题目描述

题目链接：跳跃游戏 II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置在下标 0。

每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处：

  • 0 <= j <= nums[i] 且
  • i + j < n

返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1。

示例：

1
2
3
4
5
6
7
8
9
10
11
示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

提示：

  • 1 <= nums.length <= 10^4
  • 0 <= nums[i] <= 1000
  • 题目保证可以到达 n - 1

💡 解题思路

方法一：贪心算法

其实核心思想只有一句话：

在当前可达范围内，找到下一步可达的最大范围。

从覆盖范围出发，不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最少步数。这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。

如果移动下标达到了当前这一步的最大覆盖最远距离了，还没有到终点的话，那么就必须再走一步来增加覆盖范围，直到覆盖范围覆盖了终点。

这里有个特殊情况需要考虑，当移动下标达到了当前覆盖的最远距离下标时

  • 如果当前覆盖最远距离下标小于集合终点，步数就加一，还需要继续走。
  • 如果当前覆盖最远距离下标大于等于集合终点，步数不用加一，因为不能再往后走了。

方法二：暴力解法

我们的目标是到达数组的最后一个位置，因此我们可以考虑最后一步跳跃前所在的位置，该位置通过跳跃能够到达最后一个位置。

如果有多个位置通过跳跃都能够到达最后一个位置，那么我们应该如何进行选择呢？直观上来看，我们可以“贪心”地选择距离最后一个位置最远的那个位置，也就是对应下标最小的那个位置。因此，我们可以从左到右遍历数组，选择第一个满足要求的位置。

找到最后一步跳跃前所在的位置之后，我们继续贪心地寻找倒数第二步跳跃前所在的位置，以此类推，直到找到数组的开始位置。

🔧 代码实现

1、贪心算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int jump(vector<int>& nums) {
        // 只有一个元素，直接返回
        if (nums.size() == 1) return 0;
        // 记录当前可以跳到的最远下标、下一步可以跳到的最远下标
        int currentDistance = 0, nextDistance = 0, n = nums.size(), step = 0;
        // 防止越界，且题目保证一定可以到达，因此 i < n
        for(int i = 0; i < n; i++) {
            // 在当前可以跳到的最大下标范围内，找下一次可以跳到的最大下标（骑驴找马）
            nextDistance = max(i + nums[i], nextDistance);
            // 到了当前可以跳到的下标了，我们跳一步
            if (i == currentDistance){
                step++;
                // 更新当前可以跳到的最大下标
                currentDistance = nextDistance;
                // 如果已经可以到达终点，直接break
                if (nextDistance >= n - 1) break;
            }
        }
        return step;
    }
};

2、暴力解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int jump(vector<int>& nums) {
        int position = nums.size() - 1;
        int steps = 0;
        while (position > 0) {
            for (int i = 0; i < position; i++) {
                if (i + nums[i] >= position) {
                    position = i;
                    steps++;
                    break;
                }
            }
        }
        return steps;
    }
};

📊 复杂度分析

1、贪心算法

  • 时间复杂度：O(n)O(n)，其中 nn 是数组长度。
  • 空间复杂度：O(1)O(1)。

2、暴力解法

  • 时间复杂度：O(n2)O(n^2)，其中 nn 是数组长度。有两层嵌套循环，在最坏的情况下，例如数组中的所有元素都是 11，position 需要遍历数组中的每个位置，对于 position 的每个值都有一次循环。
  • 空间复杂度：O(1)O(1)。

🎯 总结

  • 核心思想：骑驴找马思想。