题目描述

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.

思路分析

需要用贪心算法的思想，在递归的过程中记录当前这一跳能跳的最远位置和下一跳能跳的最远位置（为了在跳数加了以后更新当前能跳最远位置）

算法执行过程

代码实现

public class Solution {

    /**
     * 92 / 92 test cases passed.
     *  Status: Accepted
     *  Runtime: 11 ms
     *
     * @param nums
     * @return
     */
    public int jump(int[] nums) {
        int jump = 0; // 当前跳数
        int last = 0; // 表示当前这一跳的范围，超过这个范围就会导致跳数++
        int cur = 0; // 表示能预判到的最远的地方，是通过当前位置的nums[i]来预判的
        for (int i = 0; i < nums.length; ++i) {
            if (i > cur) {  
                // 有可能无论怎么跳，都不能到达终点或者越过终点，比如[3,2,1,0,4]
                return -1;
            }
            // 需要进行下次跳跃，则更新last和当执行的跳数jump
            if (i > last) {
                last = cur;
                ++jump;
            }
            // 记录当前可达的最远点
            cur = Math.max(cur, i+nums[i]);
        }

        return jump;

    }
}