题解 | #跳跃游戏(二)#

贪心思想：时间复杂度O(N), 空间复杂度O(1)。

「C++ 代码」

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int maxJumpGrade(vector<int>& nums) {
        
        int n = nums.size();
        if(n==0)    return -1;
        // pre指示能跳跃到最后元素的最早元素，初始化状态是最后一个元素
        int pre = n-1;
        int res = nums[n-1];
        for(int i=n-2; i>=0; --i){
            if(i+nums[i] >= (pre)){
                res += nums[i];
                pre = i;
            }
        }
        // 只有pre等于0说明从第一个元素开始跳跃能够走到最后，否则直接返回-1
        return pre==0 ? res : -1;
    }
};