LeetCode 55 跳跃游戏
中等偏下
https://leetcode.cn/problems/jump-game/description/?envType=study-plan-v2&envId=top-interview-150
思路
从左向右遍历,维护preFar表示已经遍历的位置所能到达的最远下标,
最后比较 preFar 和n-1的关系即可
class Solution {
public boolean canJump(int[] nums) {
int preFar = 0;
// 遍历到 n-2 的位置, 检查preFar是否能到 n-1 即可
for (int i = 0; i < nums.length - 1; i++) {
// 此时preFar是 i-1 之前的最远位置
if (preFar < i) {
return false;
}
// 更新preFar, 包含i这个位置
preFar = Math.max(preFar, i + nums[i]);
}
return preFar >= nums.length - 1;
}
}