LeetCode 45. 跳跃游戏 II

LeetCode 45. 跳跃游戏 II

思路：
用end记录最远的跳跃位置，MaxJump记录未到end之前的最远跳跃位置，然后用MaxJump去更新end，每次i走到最远的跳跃位置end就更新一次cnt。

代码:

class Solution {
public:
    int jump(vector<int>& nums) {
        int n=nums.size();
        int MaxJump=0;
        int end=0;//最远的跳跃位置
        int cnt=0;//记录最少的跳跃次数
        for(int i=0;i<n-1;i++){
            MaxJump=max(MaxJump,nums[i]+i);
            if(i == end){
                end=MaxJump;
                cnt++;
            }
        }
        return cnt;
    }
};