45. 跳跃游戏 II

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
说明:

假设你总是可以到达数组的最后一个位置。

本题是典型的贪心算法，虽然难度是困难，但是个人认为难度并不是那么大。
回到问题本身，我们要跳最少的次数，那就要保证你每次跳到的地方，它能到达的数组位置是最远的。因为能够到达最远的点就说明他能达到所有其他点能到达的点，而其他点却到不了它能到的点。
我们举个例子
[2,3,1,1,4] 以这个数字为例子。
起点是2，能到的点一个是3，一个是1，3这个点能到的地方有1，1，4这三个地方，而1这个点只能到1这个点。
虽然表面上看2直接跳到1比2跳到3跳的更远，但是如果1不是结尾的话，那么3能够选择的点更加多，事实上也是这样的，当跳到3的时候只要再跳一步就能到达结尾，而1还需要跳两步。
这就是贪心算法的核心思想，那么代码也就呼之欲出了
JAVA实现

class Solution {
    public int jump(int[] nums) {
        int start=0,end=nums.length-1;
        int ans=0;

        while(start<end){
            if(nums[start]+start>=end){
                return ++ans;
            }      
            int j=start,i=start+1;
            int max_step=0;
            
            while(i<=start+nums[start]){
                if( nums[i]+i > max_step){
                    max_step=nums[i]+i;
                    j=i;
                }
                i++;
            }
            start=j;
            ans++;
        }
        return ans;
    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jump-game-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。