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. 首先我們設(shè)置不滿足題意的corner case返回Integer.MAX_VALUE
2. 接下來設(shè)置一個maxCover = 0， lastCover = 0， steps = 0。 maxCover代表我們當前能夠到達的最大距離，lastCover等于之前的maxCover，用來記錄我們在Greedy情況下每一跳的最遠范圍。
3. 從0開始遍歷數(shù)組，要注意條件是 i <= maxCover && i < nums.length
   1. 假如i > lastCover，這時候說明我們已經(jīng)超過了之前記錄的maxCover的范圍，這個時候我們必須要進行一次跳躍，所以steps++，并且我們更新lastCover = maxCover，即上一條之后，我們這一次最遠可以跳到哪里
   2. 假如i + nums[i] > maxCover， 這個時候我們更新maxCover = i + nums[i]，可以繼續(xù)進行接下來的計算
4. 當循環(huán)結(jié)束時，我們檢測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;
    }
}