Question:

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.

Thinking:

  1. I first use recursive to find every posible solution but overtime.
  2. So I aread the discussion and find the best way to do it is using greedy. 
    class Solution {
 public int jump(int[] nums) {
     if(nums == null || nums.length == 1) return 0;
     int step = 0;
     int low = 0;
     int high = 0;
     int reach = 0;
     while(high < nums.length - 1){
         step++;
         for(int i = low; i <= high; i++){
             reach = Math.max(reach, i + nums[i]);
         }
         low = high + 1;
         high = reach;
     }
     return step;
 }
}

二刷

还是使用贪心算法，一开始slow,fast都是0，而我们每次都尽力让每一步的移动最多。

class Solution {
    public int jump(int[] nums) {
        if(nums == null || nums.length == 0 || nums.length == 1) return 0;
        int slow = 0, fast = 0, result = 0, reach = 0;
        while(reach < nums.length - 1){
            result++;
            for(int i = slow; i <= fast; i++)
                reach = Math.max(reach, i + nums[i]);
            slow = fast + 1;
            fast = reach;
        }
        return result;
    }
}