题目描述

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

样例

示例:

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

算法

(贪心) $O(n)$

这道题的本质是区间覆盖，可以把$nums[i] = j$ 看作是区间$[i, i + j]$.要覆盖的范围则是$[0, n - 1]$

区间覆盖

区间覆盖的核心思想是用end表示已经覆盖了$[l, end]$的区间范围，然后在满足 $ l_i <= end $ 的区间中找到右端点最大的区间（贪心）。用这个最大的右端点扩展end，直到end被扩展到n，表$示[l, r]$都已经被覆盖。

AcWing907：区间覆盖的模板题

时间复杂度

从头到尾遍历了一遍nums数组，时间复杂度$O(n)$

C++ 代码

class Solution {
public:
    const int INF = 0x3f3f3f3f;
    int jump(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        int res = 0, end = l, i = 0, cur;
        while(end < r){
            cur = -INF;
            while(i <= end) cur = max(cur, nums[i] + i), i ++;
            res ++ ;
            end = cur;
        }
        return res;
    }
};