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;

}