55. Jump Game
//greedy 如果只是判断能否跳到终点，我们只要在遍历数组的过程中，
//更新每个点能跳到最远的范围就行了，
//如果最后这个范围大于等于终点，就是可以跳到。
public class Solution {
public boolean canJump(int[] nums) {
int max = 0, i = 0;
//max stands for the largest index that can be reached.
for(i = 0; i <= max && i < nums.length; i++){
//i<=max限制了当前可以通过max以内的步数到达 如果i>max则证明我们到不了i
max = Math.max(max, nums[i] + i);
}
return i == nums.length;
}
}
class Solution {
public:
bool canJump(vector<int>& nums) {
int size = nums.size();
int reach =0;
int i = 0;
for( i = 0;i<size && i<=reach;++i){
reach=max(i+nums[i],reach);
}
return reach>=size-1;
}
};