Jump Game II

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.)

Analysis

• 自顶向下Greedy approach
• 维护 start - end 区间
• end: 之前start到end可以覆盖到的最远
• start: 之前end+1
• 当end>length时, return jump的步数

Example 1:
 1   2   1   3   2   2   2   4   1   6        count
S,E                                             0
    S,E                                         1
         S   E                                  2
                 S       E                      3
                             S   E              4
                                     S     E-->return 5

Example 2:
 2   3   1   1   4                count
S,E                                 0
     S   E                          1
             S   E-->return         2

• end代表跳n步可以跳到的最远的距离，算的方法就是把n-1步可以走到的范围加上最大步数比较一遍
• 为什么start算作之前一步的end+1?之前的已经算过，不用再算了。

Code

public class Solution {
    public int jump(int[] nums) {
        int start = 0, end =0, count =0;

        if (nums.length==1) return 0;

        while (end < nums.length){
            int max = 0;
            count++;
            for (int i=start; i<=end; i++){
                max=Math.max(max, nums[i]+i);
                if (max >= nums.length-1) return count; //注意这里不能用break，因为要break两个循环
            }
            start = end+1;
            end = max;
        }
        return count;
    }
}

Reference

• Yuanbin
• Fish