题目描述

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

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

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

示例:

输入: [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] && 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] && 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;
    }
}