[力扣100] 45.跳跃游戏||

index.php/tags-41973.html" >���加链接描述

思路：

1. 从后往前找：必到最后一个下标，最后一个下标来自于之前的下标跳跃过来
2. 如果有多个点都能跳到最后一步，那么选择离最后一步最远的下标，这里理所应当的就顺应的从左到右遍历数组
3. 依次倒数第二步，倒数第三步…知道position变成0为止

class Solution:    def jump(self, nums: List[int]) -> int:        # 从后向前推导，如果有多个位置能到达最后一个位置，选择一个最远的        steps=0        position=len(nums)-1        while position>0:   #如果position等于0就是从开始            for i in range(position):                if i +nums[i]>=position:                    position=i                    steps+=1                    break                return steps

思路二：

1. 从前向后遍历，记录每一次能跳跃到的最大下标
2. 把这个最大下标记为边界，从左到右遍历数组，到达边界时，更新边界并将跳跃次数增加 1
3. 这个思路不清晰

class Solution:    def jump(self, nums: List[int]) -> int:        n = len(nums)        maxPos, end, step = 0, 0, 0        for i in range(n - 1):            maxPos = max(maxPos, i + nums[i])            if i == end:                end = maxPos                step += 1        return step