题目描述

给定非负整型数组，初始时你在第一个元素的位置上。每个元素代表每次可以跳跃的最大长度。

判断是否可以跳到数组末尾。

样例

输入：[2,3,1,1,4]
输出：true

输入：[3,2,1,0,4]
输出：false

算法

(贪心递推) $O(n)$

1. 仿照 Jump Game II 的算法。
2. 特别地，在 while 循环中，限制 last 严格小于 i。否则，如果发现 i 之前所有位置均无法到达 i，则直接返回 false。
3. for 循环成功结束意味着每个位置均可以到达，返回 true。

时间复杂度

• 数组的每个元素最多被遍历两次，故时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        int last = 0;

        for (int i = 1; i < n; i++) {
            while (last < i && i > last + nums[last])
                last++;

            if (last == i)
                return false;
        }

        return true;
    }
};