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

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

思路：

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