P106 跳数组

描述#

这个题目说的是，给你一个非负整数数组，数组中的每个数字表示那个位置上可以向后跳的最大步数。一开始你站在下标为 0 的位置，你要判断是否可以跳到数组最后的位置。

比如说，给你的数组 a 是：
2, 4, 0, 1, 2
一开始站在下标为 0 的位置，最多能向后跳 2 步。你先跳 1 步，来到 4，再跳 3 步就到达最后的位置。所以要返回 true。
再比如说，给你的数组是：
2, 1, 0, 4
一开始如果跳 2 步，到达 0，不能再跳。一开始如果跳 1 步，到达 1，可以向后再跳 1 步。但跳 1 步后仍然到达 0，不能再跳。因此对于这个数组，你没办法跳到最后的位置，返回 false。

代码#

public class AlgoCasts {

  // Time: O(n), Space: O(1)
  public boolean canJumpToLast(int[] nums) {
    if (nums == null || nums.length == 0) return false;
    int n = nums.length, max = 0;
    for (int i = 0; i < n; ++i) {
      if (max >= n-1) return true;
      if (i > max) return false;
      max = Math.max(max, i+nums[i]);
    }
    return false;
  }

}