题目描述

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

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

判断你是否能够到达最后一个位置。

样例

示例 1:

输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
示例 2:

输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

算法

(贪心) $O(n)$

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

区间覆盖

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

AcWing907：区间覆盖的模板题

时间复杂度

本题不需要对区间进行排序，所以遍历了一遍数组，时间复杂度为$O(n)$

C++ 代码

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