45. 跳跃游戏 II

题目描述 给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 示例: 输入: [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。   从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。 说明: 假设你总是可以到达数组的最后一个位置。 https://leetcode-cn.com/problems/jump-game-ii/ 解法1 解法1是采用贪心解法,解法1很啰嗦,目的是尽可能让我们容易理解。策略是这样的,我们计算nums[i] + i,物理意义代表从当前出发能到达的最远位置。我们尽可能使下一跳落到较远的位置,这样才能使得跳到终点的步数最少。 我们以例子“[2,3,1,1,4]”为例,计算nums[i]+i -> nums[i],nums被更新为“[2,4,3,4,8]”,代表我站在第0个位置上,最远能跳到第2个位置上;站在第1个位置上,最远跳到第4个位置上(也就是终点),站在第2个位置上,最远能跳到第3个位置上……以此类推。那我们从0出发,最远能跳到第二个位置上,也就是说我们可以跳到第1个位置,也可以跳到第2个位置上。我们发现从第一个位置出发最远能到4,而从第2个位置出发最远能跳到3。我们刚刚说过,要保证下一跳落到较远到位置,所以我们选择从0跳到1,接着我们发现从1可以直接到终点,那么我们从1跳到4。 注意,不要落入一个误区:不是使本跳跳的尽可能远,而是从本跳出发,选择一个落脚点,从这个落脚点出发到达的尽可能远。以上面的为例,第一步我们从0跳到2虽然走的比0跳到1远,但是接下来从2出发最多只能到达3,而从1出发我们直接能到达终点。 根据上面的分析,我们能写出如下的代码,时间复杂度与空间复杂度均为O(n)。虽然这个代码包含双重循环,但是内层循环会改变外层循环的计数器,实际上只扫描了一次。 其实,上面的代码还可以继续优化,我们不需第一次扫描,将第一次扫描的逻辑合并到第二次扫描。 解法2 解法2很巧妙,但思想和解法1是差不多的。我们首先计算从当前位置i出发能到到达的最远距离,记为upperBound;我们还使用了另一个变量lastStepBound,记录从上一跳出发能到达的最远位置,最后我们使用res变量记录花费了几跳。我们接下来从i+1出发,继续更新upperBound,直到走到lastStepBound,然后我们更新lastStepBound = upperBound. 我们从i+1出发走到 lastStepBound,是为了寻找更远的下一跳。 我们以“[2,3,1,1,4]”为例,初始化lastStepBound = 0, upperBound = 0. 我们从i=0出发,更新upperBound = max(upperBound, i+nums[i]) = 2,然后我们更新lastStepBound = 2(第一跳起跳, res++),表示我们从0出发最远能到达2。接下来走到i=1更新upperBound = 4;走到i=2发现最远能到达3,则不更新upperBound。这时我们碰到了lastStepBound,得知我们下一跳最远能跳到4,另lastStepBound=upperBound(第一跳落地,第二跳起跳 res++)。当i=3时更新upperBound失败,此时i…

Read more