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.

For example:

Given array A = [2,3,1,1,4]

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.

一刷
题解：

1. 首先我们设置不满足题意的corner case返回Integer.MAX_VALUE
2. 接下来设置一个maxCover = 0， lastCover = 0， steps = 0。 maxCover代表我们当前能够到达的最大距离，lastCover等于之前的maxCover，用来记录我们在Greedy情况下每一跳的最远范围。
3. 从0开始遍历数组，要注意条件是 i <= maxCover && i < nums.length
   1. 假如i > lastCover，这时候说明我们已经超过了之前记录的maxCover的范围，这个时候我们必须要进行一次跳跃，所以steps++，并且我们更新lastCover = maxCover，即上一条之后，我们这一次最远可以跳到哪里
   2. 假如i + nums[i] > maxCover， 这个时候我们更新maxCover = i + nums[i]，可以继续进行接下来的计算
4. 当循环结束时，我们检测maxCover是否 >= nums.length - 1
   1. 假如成立，则说明我们可以到达右边界，这时候返回steps
   2. 否则我们返回Integer.MIN_VALUE

Time Complexity - O(n)， Space Complexity - O(1)

public class Solution {
    public int jump(int[] nums) {
        if(nums == null || nums.length == 0) return Integer.MAX_VALUE;
        
        int maxCover = 0, lastCover = 0, steps = 0;
        for(int i=0; i<=maxCover && i<nums.length; i++){
            if(i>lastCover){
                lastCover = maxCover;
                steps++;
            }
            if(i + nums[i] > maxCover) maxCover = i+nums[i];
        }
        
        return maxCover>=nums.length-1? steps:Integer.MAX_VALUE;
    }
}

二刷
maxCover是i + num[i]的最大值。lastCover是上一次的maxCover, 如果i超出了lastcover, 那么step++, 更新maxCover

public class Solution {
    public int jump(int[] nums) {
        if(nums == null || nums.length == 0) return Integer.MAX_VALUE;
        int lastCover = 0, maxCover = 0, step = 0;
        for(int i=0; i<=maxCover && i<nums.length; i++){
            if(i>lastCover){
                lastCover = maxCover;
                step++;
            }
            maxCover = Math.max(maxCover, i+nums[i]);
        }
        
        return maxCover>=nums.length-1? step:Integer.MAX_VALUE;
    }
}