跳跃游戏

跳跃游戏

55. 跳跃游戏

问题描述

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。

示例

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

输出：true

解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

分析问题

这道题是判断能否到达最后一个下标，换句话说，就是最远能跳到的位置是否大于等于数组的最后一个下标（如果能到达某个位置，那一定能到达它前面的所有位置）。

我们可以使用贪心法来求解。还记得我们的贪心算法的求解步骤吗？我们这里直接套模板~

1. 对于求解如下问题时，首先要联想到贪心算法

   给定一组数据，我们从中选出一些数据，使得满足限制条件的前提下，期望值取得最大。以给定的例子为例，没有限制条件，期望值就是最远能跳到的位置。

2. 尝试看一下这个问题是否能用贪心法来求解

   每次选择当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大的数据。以给定的例子为例，在每走一步的过程中，尽可能到达的最远位置（贪心，局部最优）。

3. 我们举几个例子来验证一下贪心算法产生的结果是否是最优的。

   我们这里也举不出反例，所以我们不妨来用贪心求解试试。

下面我们直接看代码实现。

class Solution:
    def canJump(self, nums):
        n=len(nums) #数组的长度
        max_num=0 #初始化最远可以到达的位置
        #遍历数组中的每一个位置
        for i in range(n):
            #如果该位置在最远可以到达的位置的范围内
            if i <= max_num:
                #更新最远可以到达的位置
                max_num = max(max_num, i + nums[i])
                #如果最远可以到达的位置大于数组的最后一个位置的下标，则返回True
                if max_num >= n - 1:
                    return True
        return False

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