由于题目已经告诉了我们一定可以跳到,所以我们只需去考虑前进最快的方法。即 判断当前下一步能跳的各个位置中,哪个能带你去去向最远的地方(why? 因为其他位置所能提供的最大范围都没最远那个大,所以最远的那个已经可以囊括所有其他范围)
代码如下:
class Solution {
public:
int jump(vector<int>& nums) {
int n=nums.size();
int step=0;
int u=0;
int u_max=0;
int step_size=0;
int max_size=0;
int loci=0;
int count=0;
while(step<n-1){
count++;
step_size=nums[step];
max_size=step+step_size;
if(max_size>=n-1)return count;
for(int i=1;i<=step_size;i++){
u=step+i+nums[step+i];
if(u_max<u){
u_max=u;
loci=step+i;
}
}
step=loci;
}
return count;
}
};