跟正常的跳跃游戏差不多,每次都记录下一次可跳跃的最大距离,当前i值达到当前最大可跳跃距离时就继承下一次可跳跃最大距离,这个时候再将步数+1
总体的贪心策略就是每次都在当前可跳跃范围内选择一个下一次可以覆盖更广的点进行跳跃
class Solution {
public:
int jump(vector<int>& nums) {
int result=0;
int curCover=0,nextCover=0;
//循环到size-1是为了通过用例【0】
for(int i=0;i<nums.size()-1;i++){
nextCover=max(i+nums[i],nextCover);
if(i==curCover){
curCover=nextCover;
result++;
if(curCover>=nums.size()-1)
break;
}
}
return result;
}
};