今天在刷leetcode的每日一题的时候，发现了一道有意思的题目，题目链接，题目原文如下：
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
这是一道被定性为复杂的问题，让我们来尝试一波，看看如何解决掉它
方法1:
乍一看题目，我第一个想法就是利用递归去尝试遍历所有的可能性，并把能正确到达的都记录下来，然后再从结果集里面找出最小的遍历次数。在此我简单阐述一下我的想法，首先从开始位置，拿到下一次递归的最大步长，然后去子数组里面寻找对应位置，当发现最大步长已经可以走到最后元素的时候，步数加一齐活，回退到上层调用，重新找新的可能性，依次类推，直到全部都遍历一遍，产生一个结果集，再从中寻找最小值就好啦。代码如下：
优点：想法简单，从理解到书写都相对简单直接
缺点：时间复杂度高，如果数组量较大，容易得到leetcode编译器超时警告⚠️。
鉴于已经获得超时警告，我们肯定是不甘于就此打住的，所以我们可能需要另辟蹊径来解决这个问题，由此产生了下面的方法
方法2:
经过了一轮尝试，我们可能发现了一个规律，就是每次我们都想找那个能一步到最后的位置，找到了它，我们就好继续寻找遍历的方向。类似贪心算法，每次我们都能找到最远的地方，那我们就可以快乐的出发了，代码如下：
优点：简单快速，我们可以从后向前的陆续找到最早出现跨越最长的点，然后记录下它们以使得我们能更快的跨过整个数组
缺点：时间复杂度O(N^2)，这就是我们碰到的最大的问题
方法3：
对于这样的时间复杂度，我们肯定是不能满足的，所以我去看了一下官方提供的题解，简单的搬运过来和大家分享。官方提到了我们可以通过贪心算法来正面求解，即每一步我们都准备一个围栏，来记录下这一步内的各点能达到的最远处，之后循环遍历各个位置，来帮助我们最快速的找到需要步数最少的结果，以下图为例（来源于leetcode）：
我们从下标0的位置，最大可以达到下标为2的位置，所以我们把下标2作为一个围栏，我们要找到的就是下一个结点到围栏结点之间，能走到的最远的位置。待全部遍历完，就可以步数加一，更新围栏结点，继续遍历后面的部分了（注意：此时的开始位置就是旧围栏的后一个结点），直到全部遍历完数组，就可以获得最小的步数了，代码如下（因官方给出的更为简洁，故此处使用官方代码展示）：
优点：时间复杂度O(N)
缺点：对于初次碰到这个问题的我，可能没有找到特别好的直接联想到这个方法的入口，需要提升我自己的代码技艺
好了，今天的问题就解到此了，未来争取每天刷一道leetcode，有问题来找我交流，希望能从大家那里学到更多
QQ: 314993822
Email: hebut_moros@foxmail.com
