Contents

1. 1. 题意：

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

题意：

从左边往右边跳，用最小的步数跳到最右边，到i点时，下次能跳的最远距离为A[i]

• 参考：http://blog.csdn.net/feliciafay/article/details/42779827

class Solution {
public:
    int jump(vector<int>& nums) {
        if(nums.size() == 1){
            return 0;
        }
        int n = nums.size();
        /*            step 跳的步数            index 当前位置i与跳出nums[i]距离范围内的点            distance 目前在的位置            rightest_distance 下次能跳到的最远边界        */
            step 跳的步数
            index 当前位置i与跳出nums[i]距离范围内的点
            distance 目前在的位置
            rightest_distance 下次能跳到的最远边界
        */
        int step = 1, index = 0, distance = nums[0];//初始化第一次跳
        while(distance < n-1){
            int rightest_distance = distance;
            while(index <= distance && index < n){//扩展下次能跳到的最远边界
                rightest_distance = max(rightest_distance, index + nums[index]);
                index++;
            }
            if(rightest_distance <= distance){//nums数组里有负数，则不符合，返回-1代表失败
                return -1;
            }
            distance = rightest_distance;//更新下次能跳到的最远边界
            step++;//跳跃到能跳到的最远边界
        }
        return step;//最后一跳，到达或超过终点
    }
};