[LeetCode 45] Jump Game II (hard

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： 需要理解透彻！！！

1. 需要三个变量

• Step: 记录当前走的步数
• currentMax: 当前这一步，最远等达到的位置
• nextMax：当前这步的计算过程中，根据nums[i] + i，得到的下一步可以到达的最远距离

2. 遍历数组，当index <= currentMax，不断更新nextMax。当index == currentMax，说明从不同起点走的当前步已经走完。

while (index <= currentMax) {
                nextMax = Math.max (nextMax, nums[index] + index);
                index++;
            }

3. 然后更新currentMax: currentMax = nextMax

4. Step++

5. 判断如果currentMax >= nums.length - 1, 说明可以到达尾部，直接返回step

6. NOTE：需要处理一种特殊情况，比如[2,1,3,1,1,0,1]
   当走到0时，index++以后index == 6, 但是因为0的存在所以nextMax ==5, ==> currentMax ==5. 无论如何都到不了尾部，就需要跳出循环了。最终返回0，无法到达尾部。

class Solution {
    public int jump(int[] nums) {
        if (nums == null || nums.length <= 1)
            return 0;
        
        int step = 0;
        int currentMax = 0;
        int nextMax = 0;
        int index = 0;
        
        while (index <= currentMax) {
            
            // update nextMax for each step
            while (index <= currentMax) {
                nextMax = Math.max (nextMax, nums[index] + index);
                index++;
            }
            
            currentMax = nextMax;
            step ++;
            
            if (currentMax >= nums.length - 1)
                return step;
        }
        
        return 0;
    }
}