45. Jump Game II (1)

Link

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example:

Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
    Jump 1 step from index 0 to 1, then 3 steps to the last index.

Note:

You can assume that you can always reach the last index.

Solution

針對除了最後一個node外的所有node進行調查，找到iteration過程中計算每個點能夠到的最遠位置。

並與目前為止能到的最遠的點進行比較，若大於目前最遠能到的點的紀錄，就更新他。

如果列舉的index​ 已經到達上輪jump所能到的最遠能到的點，就進行一次新的jump並將最遠能到的點更新成本次這輪能jump到最遠位置。

 public int canJumpII(int[] nums) {
        int currentPosition = 0;
        int farestPosition = 0;
        int jump = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            farestPosition = Math.max(farestPosition, nums[i] + i);
            if (i == currentPosition) {
                jump++;
                currentPosition = farestPosition;
            }
        }
        if (currentPosition >= (nums.length - 1)) {
            return jump;
        }
        return -1; //can't visit to the last index
}