我的个人博客

45. 跳跃游戏 II

0位置可以跳到的区间为[p,q]，在到达q时，从0位置一定跳到[p,q]中某一位置从[p,q]中某一位置可以到达的最远位置为maxPos
从绿色区间、蓝色区间分别进行一次跳跃

class Solution {
public:
    int jump(vector<int>& nums) {
        int step=0;
        int maxPos=0; //当前可以达到的最远位置
        int limit=0;

        for(int i=0;i<nums.size()-1;i++){
            maxPos=max(maxPos,i+nums[i]);
            if(i==limit){
                step++;
                limit=maxPos;
            }
        }
        return step;
    }
};