给出一个非负整数数组，你最初在数组第一个元素的位置
数组中的元素代表你在这个位置可以跳跃的最大长度
你的目标是用最少的跳跃次数来到达数组的最后一个元素的位置
例如
给出数组 A =[2,3,1,1,4]
最少需要两次才能跳跃到数组最后一个元素的位置。（从数组下标为0的位置跳长度1到达下标1的位置，然后跳长度3到数组最后一个元素的位置）
思路：
当所处于一个位置i时 它能到达的区间是i 到 i+A[i]之间
也就是对于任何一个位置 它所能到达的最远位置 max_pos=i+A[i]
那么从起点开始
维护两个变量 max_pos_pre 即上一个跳点 所包含的范围（以最远点描述）max_pos_cur 记录途中每个点所能到达最远位置当i>max_pos_pre也就是每搜索完上一个点的区间时，那么step++ 跳到途中最远点的所处范围用max_pos_pre=max_pos_cur进行描述int jump(int* A, int n) { // write code here if(n==0) return 0; int step=0; int max_pos_pre=0; int max_pos_cur=0;//记录中途分段搜索的过程中每一段 中数字所能到达的最远处 // 可以证明 后一段的最远处一定比前一段最远处 更远 for(int i=0;i<n;i++) { if(i>max_pos_pre) //跳过了之前的区间 { step++; max_pos_pre=max_pos_cur; if(max_pos_pre>=n-1) return step; } max_pos_cur=max(max_pos_cur,i+A[i]); } }
