LeetCode55. 跳跃游戏
方法:贪心算法
假设一步一步走,每次记录他从当前位置到达的最远地址与前面保存的最大地址比较,保留最大值,若遍历到当前位置大于最大值,说明前面无论怎么走都到达不了该位置,返回false,遍历到结尾返回true
class Solution {
public:
bool canJump(vector& nums) {
int max_index = 0;
for(int i=0;i<nums.size();i++){
if(max_index < i)
return false;
max_index = max(max_index,i + nums[i]);
}
return true;
}
};