55. Jump Game 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean canJump(int[] nums) {    
        int start = 0, end = nums[0]; // [start, end]
        while (end < nums.length - 1) {
            int nextEnd = end;
            for (int i = start; i <= end; i++) {
                nextEnd = Math.max(nextEnd, i + nums[i]);
            }

            if (nextEnd == end) {
                return false;
            }

            start = end + 1;
            end = nextEnd;
        }

        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean canJump(int[] nums) {
        int rightmost = 0; // [0, rightmost]

        int j = 0;
        while (j <= rightmost) {
            rightmost = Math.max(rightmost, j + nums[j]);

            if (rightmost >= nums.length - 1) {
                // 注意题目要求跳跃至最后一个元素即算成功，而不是跳出数组
                return true;
            }

            j++;
        }

        return false;
    }
}

关键点在于遍历时不能遗漏中间的元素，因为中间元素可以跳跃的范围可能很大。

References

55. Jump Game