题解 | #牛群跃迁# 贪心

知识点

贪心

思路

我们发现，我们始终存在这一个可以到达的右边界r，因此我们可以维护这个右边界，并且从左到右遍历，一旦当前位置超出了右边界而且还没到末尾，说明不能满足条件，反之可以满足条件。

时间复杂度

AC Code（C++）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return bool布尔型
     */
    bool can_jump(vector<int>& nums) {
        int n = nums.size();
        int r = 0;
        for (int i = 0; i < n; i ++) {
            if (r < i) return false;
            r = max(r, i + nums[i]);
        }
        return true;
    }
};