贪心算法

思路:尽可能到达最远位置(贪心)
如果能到达某个位置,那一定能到达它前面的所有位置。
方法:初始化最远位置为 0,然后遍历数组,如果当前位置能到达,并且当前位置+跳数>最远位置,就更新最远位置。如果当前位置比最远位置还要远,直接返回False。

复杂度分析:
时间复杂度 O ( n ) O(n)O(n),空间复杂度 O ( 1 ) O(1)O(1)

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # 最远到达位置
        reach = 0
        for i in range(len(nums)):
            if i > reach: return False
            reach = max(reach, i + nums[i])
        return True