跳跃游戏II

跳跃游戏II

读前福利，最全pdf获取

45. 跳跃游戏 II

问题描述

给你一个非负整数数组 nums ，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。假设你总是可以到达数组的最后一个位置。

示例：

输入：nums = [2, 3, 1, 1, 4]

输出：2

解释：跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

分析问题

这道题是上一题的升级版本，我们一样可以采用贪心算法来求解，在每走一步的过程中，寻找尽可能到达的最远位置（局部最优）。

例如对于数组 nums = [2, 3, 1, 1, 4] ，初始位置是下标 0，从下标 0 出发，最远可到达下标 2，即可跳的范围如下图所示的粉色节点。因为此时下标 1 的值是 3，从下标 1 出发可以达到更远的位置，所以第一步到达下标 1。

在具体的实现中，我们维护当前能够到达的最大下标位置，记为边界。我们从左到右遍历数组，到达边界时，更新边界并将跳跃次数增加 1。

这里有一个小的细节需要注意，在遍历数组时，我们不访问最后一个元素，这是因为在访问最后一个元素之前，我们的边界一定大于等于最后一个位置，否则就无法跳到最后一个位置了。如果访问最后一个元素，在边界正好为最后一个位置的情况下，我们会增加一次「不必要的跳跃次数」，因此我们不必访问最后一个元素。

下面我们来看一下代码的实现。

class Solution:
    def jump(self, nums):
        n = len(nums)
        #代表边界位置
        end = 0
        #最远可以到达的位置
        max_num=0
        step=0
        for i in range(n - 1):
            if max_num >= i:
                max_num = max(max_num, i + nums[i])
                if i == end:
                    end = max_num
                    step += 1
        return step

该算法的时间复杂度是O(n)，空间复杂度是O(1)。