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

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

0 <= j <= nums[i] 且

i + j < n

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

示例 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 步：最少步数 → BFS。 每次跳跃代价相同，“最少几跳”就是最短路，无权图最短路就是 BFS。

第 2 步：把数组看成图。 节点是下标，i 连向 i+1 … i+nums[i]。

BFS 第 k 层 表示 恰好 k 跳能到的所有下标，答案就是 n-1所在的层数。

第 3 步：关键观察——每层是连续区间。 从一段连续下标出发，能到的还是一段连续下标。所以 BFS的每一层不用存集合，只用两个数：当前层右端 end、下一层右端 maxP。

第 4 步：扫一遍数组 = 逐层出队。 i 在当前层内右移时不断算 maxP = max(maxP, i + nums[i])；i 走到 end说明当前层耗尽，换层，步数 +1。

想要以最少的步数到达最后一格，理论上每步需要尽可能的跳远点

所以我们可以维护一个最远边界值，每次到达最远边界时才加上一步

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int jump(vector<int> &nums) {
        int n = nums.size();
        int ans = 0;
        int maxP = 0;
        int end = 0;
        for (int i = 0; i < n - 1; i++) {
            if (maxP >= i) {
                maxP = max(maxP, i + nums[i]);
                if (i == end) {
                    end = maxP;
                    ans++;
                }
            }
        }
        return ans;
    }
};