45. 跳跃游戏 II - 力扣(LeetCode)
贪心找可以跳的范围里 这些点最远可以跳到哪里 , 跳的越远选择机会越多
例如 : 3 2 3 0 2 6 1 2
从[0] 开始 : 可以跳到 3 2 3 0 2 6 1 2
跳到[1] , 也就是2 , 它下一步可以跳到 下标 2+[1] = [3]
跳到[2] , 也就是3 , 它下一步可以跳到 下标 3+[2] = [5]
跳到[3] , 也就是0 , 它下一步可以跳到 下标 0+[3] = [3]
就选 跳到[2] , 这样可以跳的最远,下一次选择的机会也多
用next记录 可以跳的范围内 最远可以跳到哪里
class Solution {
public:int jump(vector<int>& nums) {int next=0;//可以跳的点里 , 可以跳到的最远距离int cur=0;//当前下标int ans=0; //跳跃次数int m=0;//找可以从当前位置跳最远的for(int i=0;i<nums.size();i++){if(cur < i){ans++;cur = next;}next = max(next,i+nums[i]);}return ans;}
};