leetcode45. 跳跃游戏 II

1.题目描述：

给你一个非负整数数组nums，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。假设你总是可以到达数组的最后一个位置。

2.贪心算法：

与leetcode55. 跳跃游戏不同在于默认能到达最末，但是需要求出最小的次数。实际上就是求每一次跳跃动态覆盖最大范围直至能到最末位置的最大范围数目，其中也是不关注每次怎么跳，跳多远，只关注最少的次数。需要注意的是下一次length的最大范围更新，与i循环遍历到当前curLength的最末是同步的，至少不会迟于。

class Solution {
    public int jump(int[] nums) {
        int length = 0;
        int count = 0;
        int curLength = 0;
        for (int i = 0; i < nums.length - 1; i++) {//停在倒数第二个位置，简化最后一次跳跃
            length = Math.max(length, i + nums[i]);
            if (i == curLength) {
                count++;
                curLength = length;
            }    
        }
        return count;
    }
}

或：（推荐）

class Solution {
    public int jump(int[] nums) {
        if (nums == null || nums.length == 0 || nums.length == 1) return 0;
        int maxLength = 0;//下一步覆盖最大区域
        int count = 0;
        int curLength = 0;//当前覆盖最大区域
        for (int i = 0; i < nums.length; i++) {
            maxLength = Math.max(maxLength, i + nums[i]);//更新覆盖最大区域
            if (length >= nums.length - 1) {//当前再跳一步即可
                count++;
                break;
            }
            if (i == curLength) {//走到当前覆盖最大区域，并更新下一步覆盖最大区域
                count++;
                curLength = maxLength;
            }    
        }
        return count;
    }
}