利用贪心算法，从第一个位置开始，每个位置都跳到最远处，分别记录当前位置能达到的最远距离。遍历到最后一位，如果跳跃距离大于等于最后一位则可以达到最后一位。

题目

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

示例

示例 1:

输入: [2,3,1,1,4]
输出: true

解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。 示例 2:

输入: [3,2,1,0,4]
输出: false

解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

考察知识点

贪心算法、数组

核心思想

贪心算法的三个步骤

第一步、明确到底什么是最优解？
第二步、明确什么是子问题的最优解？（子问题的最优解有很多，选择一个最直接、最容易理解的方式进行定义即可。）
第三步、分别求出子问题的最优解再堆叠出全局最优解。
使用贪心算法，从第一个位置开始，每个位置都跳到最远处，分别记录当前位置能达到的最远距离。遍历到最后一位，如果跳跃距离大于等于最后一位则可以达到最后一位。

算法

• 变量声明
• 特判
• 开始循环计算
  • 如果当前终点小于当前位置，说明到不了这个位置，直接return False就行。
  • 更新max_bound
  • 如果新的最远距离大于等于最后一位，说明可以到达这里， return True。
  • 如果达到终点，就更新max_bound
• 如果循环结束也没能达到最后一位就return False

Python版本

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        max_bound = nums[0]  # 变量声明
        end = nums[0]
        n = len(nums)
        if n == 1:  # 特判
            return True
        if nums[0] == 0 or n == 0:
            return False
        # 开始循环计算
        for i in range(1, n):
            # 如果当前终点小于当前位置，说明到不了这个位置，直接return False就行。
            if end < i: return False
            # 更新max_bound
            max_bound = max(max_bound, nums[i] + i)
            # 如果新的最远距离大于等于最后一位，说明可以到达这里， return True。
            if max_bound >= n-1: return True
             # 如果达到终点，就更新max_bound
            if i == end: end = max_bound
        return False  # 如果循环结束也没能达到最后一位就return False

print("leet code accept!!!")
Input = [[1,2], [0], [2,3,1,1,4], [3,2,1,0,4]]
Input1 = [10]
Answer = [True, True, True, False]

if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)):
        print("-"*50)
        reslut = solution.canJump(Input[i])
        print(reslut == Answer[i])

时间复杂度：\(O(n)\) 。
空间复杂度：\(O(1)\) 。
执行用时 :56 ms, 在所有 Python3 提交中击败了90.28%的用户。
内存消耗 :14.8 MB, 在所有 Python3 提交中击败了60.40%的用户。