题目

贪心

简单观察即可发现，如果在某个位置停下不能继续向前跳跃，则输出 false ，因此对每一个位置遍历到它最大跳跃位置并查看是否能继续前进即可。时间复杂度 $O(n)$ ，空间复杂度 $O(1)$ ：

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size() - 1, maxn = 0;
        for(int i = 0; i < n; ++i) {
            maxn = max(nums[i] + i, maxn);
            if(maxn == i && maxn < n)
                return false;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12