leetcode：45. 跳跃游戏 II【经典贪心】

分析

已经能到达最后一个（可通过跳跃游戏1判断）
然后还是按照每次能走的区间，记录maxPos
一个个位置遍历，在能走的区间内边走边看找到下一个maxPos
然后如果当前位置i触及end（也就是上一个maxPos的位置，这是我们能走的极限）
这时候step必须加1，同时下一个的end就是我们当前记录的maxPos
极尽贪心之道

ac code

class Solution:
    def jump(self, nums: List[int]) -> int:

        # 可以用跳跃游戏1来判断是否可以到达最后一个位置
        # 这个跳跃游戏2基于1求最少到达的次数
        # 还是贪心，当前的[cur, maxPos]往前看，能走最远的才“加油”

        maxPos, mustAdd, step = 0, 0, 0
        n = len(nums)

        # 到了必须要加油的地方才加油
        # 最后一个位置是要到达，没必要加油
        for i in range(n - 1):
            # 贪心当前能走区间看到的最远位置
            maxPos = max(maxPos, nums[i] + i)
            # 如果走到必须加油的地方
            if i == mustAdd:
                # 下一次必须加油的地方
                # 就是上一段区间能看到最远的地方
                mustAdd = maxPos
                step += 1
        
        return step

总结

走当前油量能支持的所有区间
然后到每个位置边走边看，如果在这个位置加油接下来能到达的最大位置
然后在这个区间内找到下一个区间的maxPos即可