力扣网编程45题：跳跃游戏II之正向查找方法（中等）

一. 简介

前面一篇文章使用贪心算法逆向思维解决了力扣网45题：跳跃游戏II，文章如下：

力扣网编程45题：跳跃游戏II之逆向思维（中等）-CSDN博客

因为之前采用逆向推导的方法时间复杂度为O(n*n)，是比较高的，本文采用正面查找方法来解决方法，来降低时间复杂度。

二. 力扣网编程45题：跳跃游戏II之正向查找方法

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
    0 <= j <= nums[i] 
    i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

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

示例 2:
输入: nums = [2,3,0,1,4]
输出: 2

解题思路二：（正向查找可到达的最远距离）

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

这里也是使用贪心算法，正向查找跳跃次数最少的路径。

算法核心思想：

使用贪心算法的思想，通过维护两个变量来追踪跳跃过程中的位置和步数（最少跳跃次数的路径中）：

当前跳跃的最远距离（current_end）：表示当前跳跃能到达的最远位置；

下一步跳跃的最远位置（farthest）：表示在当前跳跃的基础上，下一步能够到达的最远位置；

举例说明：

具体实现思路：

1. 贪心算法：通过每一次选择能跳到的最远位置来最小化跳跃次数；

2. 维护边界：维护当前能跳跃到达的最远位置（current_end）和下一步跳跃能到达的最远位置（farthest）；

3.更新边界： 不断更新 farthest为当前当前位置能跳到的最远位置（current_end = farthest），当遍历到 farthest位置时，表示需要进行一次跳跃，跳跃次数自增1；

4.提前终止：如果current_end已经大于等于 numsSize-1这个位置，可以提前退出循环；

C语言实现如下：

//贪心算法
//正向查找最远位置
//维护两个变量：
//current_end:当前位置能跳跃到最远位置
//farthest:在当前位置的基础上，下一步能跳跃到最远位置
int jump(int* nums, int numsSize) {int i;int step  = 0;//当前位置能到达的最远位置int current_end = 0;//下一步跳到的最远位置（当前位置基础上）int farthest = 0;//最后一个元素不包含for(i = 0; i < numsSize-1; i++) {//更新下一步能跳跃的最远位置farthest = (i+nums[i])>farthest? (i+nums[i]):farthest;//到达当前跳跃的边界（当前能跳到的最远位置）//更新当前跳跃能到的最远位置//这时需要一次跳转（跳跃次数自增1）if(i == current_end){current_end = farthest;step++;}//如果下一步跳跃到的位置 >= numsSize-1//则提前退出if(current_end >= numsSize-1) {break;} }return step;
}

可以看出，正向查找方法只遍历了一次数组，算法的时间复杂度为O(n)。