題目

給定一個非負整數(shù)數(shù)組千劈，你最初位于數(shù)組的第一個位置挣棕。

數(shù)組中的每個元素代表你在該位置可以跳躍的最大長度宁玫。

你的目標是使用最少的跳躍次數(shù)到達數(shù)組的最后一個位置驮樊。

題目鏈接

示例

輸入: [2,3,1,1,4]
輸出: 2
解釋: 跳到最后一個位置的最小跳躍數(shù)是 2薇正。
     從下標為 0 跳到下標為 1 的位置，跳 1 步囚衔，然后跳 3 步到達數(shù)組的最后一個位置挖腰。

假設(shè)你總是可以到達數(shù)組的最后一個位置。

題目分析

逆向查找

題目給出的說明是總是可以到達最后一個位置练湿，所以直觀想到的第一種方法就是逆向貪心查找猴仑，從最后一位向前查找，找到可以到達最后一個元素的最遠的元素肥哎，依此循環(huán)辽俗。

這種算法的時間復(fù)雜度是$ O(n^2) $，在c語言里能通過篡诽，使用c++會超時崖飘，所以需要找到時間復(fù)雜度更低的算法。

正向查找

逆向查找雖然直觀杈女，但是復(fù)雜度高朱浴，我們依然借助貪心算法的思路，正向查找达椰，也可以找到結(jié)果翰蠢。

以2、3啰劲、1這數(shù)組為例梁沧，從第一個元素最多可以跳兩步，如果我們每次都選擇兩步之內(nèi)的最大值(能到達最遠距離的元素)蝇裤，那就可以用最小的步數(shù)到達最后一個元素廷支。

首先要寫出尋找步長內(nèi)最大值的函數(shù)：

int findmax(vector<int> nums, int left, int right){
    int res = left;
    for (int i = left; i < right; i++){
        if (nums[i] + i >= res + nums[res]) res = i;
    }
    return res;
}

然后是遍歷的過程：

int res = 0;
int pos = 0;
while (true){
    if (pos + nums[pos] >= nums.size() - 1){
        res++;
        break;
    }else {
        pos = findmax(nums, pos, pos + nums[pos]);
        res++;
    }
}

完整的過程見最后一部分埃碱。

題目解答

逆向查找

int jump(int* nums, int numsSize){
    int pos = numsSize - 1;
    int res = 0;
    while (pos > 0){
        for (int i = 0; i < pos; i++){
            if (i + nums[i] >= pos){
                res++;
                pos = i;
            }
        }
    }
    return res;
}

正向查找

class Solution {
public:
    int findmax(vector<int>& nums, int left, int right){
        int temp = left;
        for (int i = left; i <= right; i++){
            if (nums[i] + i >= nums[temp] + temp) temp = i;
        }
        return temp;
    }
    int jump(vector<int>& nums) {
        int len = nums.size();
        if (len == 1) return 0;
        int res = 0;
        int pos = 0;
        while (true){
            if (pos + nums[pos] >= len - 1){
                res++;
                break;
            }else {
                pos = findmax(nums, pos, pos + nums[pos]);
                res++;
            }
        }
        return res;
    }
};