【LeetCode热题100】--55.跳跃游戏

55.跳跃游戏

方法：贪心

对于数组的任意一个位置y，如何判断它是否可以到达？

只要存在一个位置x,它本身可以到达，并且它跳跃的最大长度为x+nums[x]，这个值大于等于y，即x+nums[x]≥y，那么这个位置y也可以到达，可以使用x+nums[x]更新最远可以到达的位置

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int rightmost = 0;
        for(int i = 0; i < n;i++){
            if(i<= rightmost){  
                rightmost = Math.max(rightmost, i + nums[i]);
                if(rightmost >= n -1){
                    return true;
                }
            } 
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15