题解 | #几步可以从头跳到尾#

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 最少需要跳跃几次能跳到末尾
     * @param n int整型 数组A的长度
     * @param A int整型vector 数组A
     * @return int整型
     */
    int Jump(int n, vector<int>& A) {
        // write code here
        int next_maxPosition=0;//设定下一步能跳多远
        int cur_position=0;//设定当前所能跳的最大位置
        int cnt=0;
        for (int i=0; i<A.size(); i++) {
            next_maxPosition=max(A[i]+i,next_maxPosition);//遍历当前所能跳的范围，找出下一步能跳的最大值
            if (i==cur_position) {//已经遍历当前所能跳的范围，该跳到next_maxPosition所指示的范围内
                cur_position=next_maxPosition;
                cnt++;//次数+1
            }
            if (cur_position>=A.size()-1) {
                break;
            }
        }
        return cnt;
    }
};