题目描述

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

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

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

示例:

输入: [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)。虽然这个代码包含双重循环,但是内层循环会改变外层循环的计数器,实际上只扫描了一次。

class Solution {
    public int jump(int[] nums) {
        // 第一次扫描,计算当前能走到的最远距离
        // 我们每次尽可能走得远,这样步数才会少
        for (int i = 0; i < nums.length; i++) {
            nums[i] += i;
        }

        int i = 0;
        int res = 0;

        while (i < nums.length - 1) {
            int maxIdx = i;
            for (int j = i + 1; j <= nums[i] &amp;&amp; j < nums.length; j++) {
                if (j >= nums.length - 1 || nums[j] >= nums[maxIdx]) {
                    maxIdx = j;
                }
            }
            // res++表示我们从i跳到下一跳;或者从i直接跳到终点
            res++;
            i = maxIdx;
        }

        return res;
    }
}

其实,上面的代码还可以继续优化,我们不需第一次扫描,将第一次扫描的逻辑合并到第二次扫描。

class Solution {
    public int jump(int[] nums) {
        int i = 0;
        int res = 0;

        while (i < nums.length - 1) {
            int maxIdx = i;

            for (int j = i + 1; j <= i + nums[i] &amp;&amp; j < nums.length; j++) {
                if (j >= nums.length - 1 || j + nums[j] >= maxIdx + nums[maxIdx]) {
                    maxIdx = j;
                }
            }

            res++;
            i = maxIdx;
        }

        return res;
    }
}

解法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 == nums.length – 2循环终止,返回res即可。注意,我们不需要走到i = nums.length-1,因为那是终点。

全部代码如下,时间复杂度和空间复杂度均为O(n).

class Solution {
    public int jump(int[] nums) {
        int upperBound = 0;
        int lastStepBound = 0;
        int res = 0;

        for (int i = 0; i < nums.length - 1; i++) {
            upperBound = Math.max(upperBound, i + nums[i]);

            if (i == lastStepBound) {
                res++;
                lastStepBound = upperBound;
            }
        }

        return res;
    }
}
pwrliang Algorithms, Array, Greedy ,

Leave a Reply

Your email address will not be published. Required fields are marked *