【题目】
给定数组 arr, arr[i] = k 代表可以从位置 i 向右跳 1~k 个距离。比如，arr[2] == 3, 代表从位置 2 可以跳到位置3、位置4或位置5。如果从位置 0 出现，返回最少跳几次能跳到 arr 最后的位置上。
【举例】
arr=[3, 2, 3, 1, 1, 4]。
arr[0] = 3, 选择跳到位置 2; arr[2] = 3, 可以跳到最后的位置，所以返回 2。
【要求】
如果 arr 的长度为 N， 要求实现时间复杂度为 O(N), 额外空间复杂度为 O(1)。
【难度】
一星
【解答】
- 整型变量 jump, 代表目前走了多少步，初始值为 1；整型变量 cur, 代表在能走 jump 步的情况下，可以到达的最远位置，初始值为 arr[0]；整型变量 next, 代表如果多走一步，可以达到的最远位置，初始值为 arr[0]。
- 从左到右遍历 arr, 假设遍历到位置 i:
- 如果 cur >= i, 说明跳 jump 步可以到达位置 i, 此时什么都不做。当 cur >= arr.length-1 时， 可直接返回 jump.
- 如果 cur < i, 说明跳 jump 步不可以达到位置 i, 此时要先多跳一步，令 jump++, cur = next.
3. next 代表着位置 i 前面的位置多跳一步可以到达的最远位置， i + arr[i] 代表着从位置 i 多跳一步可以到达的位置，两者之间的最大值 Math.max(next, i+arr[i]) 即为达到位置 i 或 位置 i 之前的位置多跳一步可以达到的最远位置, 赋值给 next.
具体代码实现请参考如下代码中的 jump 方法：
1 public class Main { 2 3 public static void main(String[] args) { 4 int[] arr = {3,2,3,1,1,4}; 5 System.out.println(new Main().jump(arr)); 6 } 7 8 public int jump(int[] arr){ 9 if(arr == null || arr.length < 2) return 0;10 int jump = 0; //表示跳跃步数11 int cur = 0; //表示跳跃 jump 步, 即当前可以到达的最远位置12 int next = 0; //表示多跳跃一步, 可以到达的最远位置13 14 for(int i = 0, len = arr.length; i < len; i++){15 if(cur < i){ //若当前不能达到位置 i, 则需要多跳一步, 并使 cur 指向多跳一步能达到的最远位置16 jump++;17 cur = next;18 if(cur >= len - 1){19 return jump;20 }21 }22 next = Math.max(next, i + arr[i]);23 }24 25 return jump;26 }27 28 }