题目

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

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

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

题目链接

示例

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

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

题目分析

逆向查找

题目给出的说明是总是可以到达最后一个位置，所以直观想到的第一种方法就是逆向贪心查找，从最后一位向前查找，找到可以到达最后一个元素的最远的元素，依此循环。

这种算法的时间复杂度是$ O(n^2) $，在c语言里能通过，使用c++会超时，所以需要找到时间复杂度更低的算法。

正向查找

逆向查找虽然直观，但是复杂度高，我们依然借助贪心算法的思路，正向查找，也可以找到结果。

以2、3、1这数组为例，从第一个元素最多可以跳两步，如果我们每次都选择两步之内的最大值(能到达最远距离的元素)，那就可以用最小的步数到达最后一个元素。

首先要写出寻找步长内最大值的函数：

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;
    }
};