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

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

「C++ 代码」

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int minJumpStep(vector<int>& nums) {
        int n = nums.size();
        // 数组长度为0时无法跳跃，返回-1
        if(n==0)    return -1;
        int step = 0;
        // end记录的是下一个跳跃位置
        int end = 0;
        // further记录的是下下一个跳跃位置
        int further = 0;
        for(int i=0; i<n-1; ++i){
            further = max(further, nums[i] + i);
            if(i == end){
                if(i == further) return -1;
                ++step;
                end = further;
            }
        }
        return further >= (n-1) ? step : -1;
    }
};