题目描述

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

例子

Input: [2,3,1,1,4] Output: 2 Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

其他

You can assume that you can always reach the last index.

解题思路

这道题是 Jump Game I 的升级版，关于上一道题的笔记可以参考 这里。 这道题的区别在于在已知我们能到达最后位置的情况下，最少需要花费多少步数。我们同样也可以采取的思路：

• 用一个变量 furthest_possible_index 维护最远能到达的位置；
• 除此之外我们还要维护一个步数 steps 变量作为最终结果；
• 用贪心的思路更新步数，首先我们用一个变量 boundary 表示从上一个起点能跳到的位置，这个变量不会实时随最远位置更新。在我们遍历超过这个位置的时候，意味着我们需要实施一次跳跃以扩展当前能到达最远的位置，所以我们用最远能到达的位置更新他，并对步数加一。（这里还隐含了一个概念，我们用最远距离更新 boundary 的时候，其实就意味着我们是从过去的位置里面挑选一个最优位置来跳跃作为起点）

代码如下：

#include <vector>

class Solution {
public:
    int jump(std::vector<int>& nums) {

        int boundary = 0; // current furthest index from last jump
        int furthest_possible_index = 0; // furthest possible index
        int steps = 0; // steps that we need to reach the end

        for (int i = 0; i < nums.size(); i++) {
            if (i > boundary) {
                // if current index has crossed the furthest index from last jump,
                // we need to select an best index from one of the previous indexes and perform a jump
                // it should increase the boundary to furthest possible index
                steps++;
                boundary = furthest_possible_index;
            }

            furthest_possible_index = std::max(furthest_possible_index, nums[i] + i);
        }

        return steps;
    }
};

• 时间复杂度： O(n)
• 空间复杂度： O(1)