45. 跳跃游戏II 【C语言 贪心算法】

和跳跃游戏1不太一样，这里用动归是超时的，我采用的是贪心的方法。时间复杂度O（n）。

贪心的主要思路：

采用三个变量

cur：表示当前要覆盖到的最大下标。

max：还没到cur之前的遍历到能覆盖到的最大下标。

res：用来表示结果。

举个例子：

[2,3,1,1,4]；

一开始将res和cur初始化为0，分别表示步数为0和下标为0。max定义为一个小量（零或负数）。

利用贪心的思想，那么一开始（下标为0的位置）我就想走到最远的地方，也就是充分利用nums[0]（也就是2）这个步长，但是，由于不知道在这个范围里面有没有更长的覆盖区间，那么，我就***先保留着这个当前最远的下标，也就是存入我的cur中。然后先看看在这个范围里面***有没有比当前最大值更大的，有的话先存到我的max中，如果遍历***到了cur（i==cur）的时候***，我就可以确定好在cur下标覆盖的范围里面我该走到多远了，也就是max（下标）。这就是循环的全部主体了。

值得注意的是我不需要遍历到最后一个，只需要遍历到倒数第二个就行了，因为到倒数第二个就已经可以确定最后结果了。

下面上代码

int jump(int* nums, int numsSize){
    if(numsSize<2)
    return 0;
    int i, j;
    int cur=0;
    int res=0;
    int max=-1;
    for(i=0;i<numsSize-1;i++)
    {
        max=max>i+nums[i]?max:i+nums[i];
        if(cur==i)
        {
            res++;
            cur=max;
        }
    }
    return res;

}