[LintCode] 117 Jump Game II 解题报告

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


思路
贪心法
维护一个能跳到的最远的值maxReach，上一次跳的最远值lastReach，和最小跳数minStep。每经过一个点，比较一下如果这个点大于上一次跳的最远的值，那么说明我们需要从上一次的跳最远的地方lastReach再跳一步。那么最小跳数minStep加一。每一次遍历的时候比较从这一点能跳到的最远的地方i + A[i]和已有的最远值maxReach，取最大，并更新。
时间复杂度O(n)。


Code
贪心

public class Solution {
    /**
     * @param A: A list of lists of integers
     * @return: An integer
     */
    public int jump(int[] A) {
        // write your code here
        int maxReach = 0;
        int minStep = 0;
        int lastReach = 0;
        for (int i = 0; i < A.length; i++) {
            if (i > lastReach) {
                minStep++;
                lastReach = maxReach;
            }
            if (i > maxReach) {
                return -1;
            }
            maxReach = Math.max(maxReach, i + A[i]);
        }
        return minStep;
    }
}