55. 跳跃游戏

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

class Solution {
public:
//一步一步跳。jump代表可以跳到的位置。max_index是牵制jump的，如果max_index>=jump，就说明可以从
//0处跳到jump处。然后jump不断+1，如果jump最后跳到了数组末尾，就说明能跳成。
    bool canJump(vector<int>& nums) {
        vector<int>index;//index数组记录每个位置最远可以跳到哪个位置。比如i=2，num[2]==1，那么从2这个位置最远可以跳到4这个位子。
        for(int i=0;i<nums.size();i++){
            index.push_back(i+nums[i]);
        }
        //max_index表示从0到jump（当前位置）最远可以跳到的位置，max_index是牵制jump的一个变量
        //因为在下面的代码中jump不断++，总会跳到数组末尾，但是前提是max_index>=jump；因为max_index表示从0处到jump处最远可到达的位置。如果max_index都调不到jump位置处，就更不可能跳到数组末尾处。那个也没必要继续进行下去了。jump也就不会到达数组末尾处。
        int max_index=nums[0];
        int jump=0;
        while(jump<index.size()&&jump<=max_index){
            if(max_index<index[jump]) max_index=index[jump];
            jump++;
        }
        //如果jump到达数组末尾，就说明在0~数组末尾之间，max_index>=jump，也就是从0处到数组末尾处可以跳到。
        if(jump==index.size()) return true;
        return false;
 
    }
};