45. 跳跃游戏 II

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

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

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

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

示例 1:

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

示例 2:

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

解题思路

核心思路是贪心算法，通过跟踪 “当前跳跃的最远边界” 和 “下一次跳跃的最远可达位置”，在每一步跳跃时选择最优范围，实现最少跳跃次数：

  1. 贪心策略：
    • 用 end 表示当前跳跃能到达的最远边界（初始为 0）；
    • 用 max_reach 表示从当前位置到 end 之间的所有位置能跳到的最远位置；
    • 用 steps 记录跳跃次数（初始为 0）。
    • 遍历数组时，在 end 范围内更新 max_reach，当到达 end 时（当前跳跃结束），执行一次跳跃（steps++），并将 end 更新为 max_reach。
  2. 关键逻辑：
    • 遍历到 n-2（最后一个元素前）即可，因为到达最后一个元素无需再跳跃；
    • 每次到达 end 时，必须执行一次跳跃（否则无法前进），且 max_reach 一定大于 end（题目保证可达终点）。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        int end = 0;          // 当前跳跃的最远边界
        int max_reach = 0;    // 下一次跳跃的最远可达位置
        int steps = 0;        // 跳跃次数
        
        // 遍历到倒数第二个元素即可（最后一个元素无需跳跃）
        for (int i = 0; i < n - 1; ++i) {
            // 更新下一次跳跃的最远可达位置
            max_reach = max(max_reach, i + nums[i]);
            
            // 到达当前跳跃的边界，必须执行一次跳跃
            if (i == end) {
                steps++;
                end = max_reach;  // 更新边界为下一次跳跃的最远位置
            }
        }
        
        return steps;
    }
};