45. Jump Game II - jiejackyzhang/leetcode-note GitHub Wiki

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.

如果用DP来解，时间复杂度为O(n^2)，会超时。

这里采用一种O(n)的方法来解，思想为greedy algorithm。 记住当前步数能到的最远的地方，然后记下在这个区域内每个格子能到的最远地方，如果超出了这个区域，则步数要加一，并更新能到的最远处。

public class Solution {
    public int jump(int[] nums) {
        int step = 0, lastJumpMax = 0, curJumpMax = 0;
        for(int i = 0; i < nums.length-1; i++) {
            curJumpMax = Math.max(curJumpMax, i + nums[i]);
            if(i == lastJumpMax) {
                step++;
                lastJumpMax = curJumpMax;
                if(lastJumpMax >= nums.length-1) return step;
            }
        }
        return step;
    }
}

另一种实现为： 记录走第i步的起始位置start和能到的最远的地方end。然后在其中遍历，i+nums[i]即为走i+1步能到的位置，更新start和end。

public class Solution {
    public int jump(int[] nums) {
        int jumps = 0;
        int start = 0, end = 0;
        while(end < nums.length-1) {
            jumps++;
            int farthest = end;
            for(int i = start; i <= end; i++) {
                if(i + nums[i] > farthest) farthest = i + nums[i];
            }
            start = end+1;
            end = farthest;
        }
        return jumps;
    }
}