思路:尽可能到达最远位置(贪心)
如果能到达某个位置,那一定能到达它前面的所有位置。
方法:初始化最远位置为 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