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

分析

维护当前走到的位置，以及当前能走的最大区间内下一次走到的最远位置maxPos
当前能走的位置就是[cur, maxPos]但是在走的过程中，边走边看下一次的maxPos，然后当cur走到上一个maxPos时，下一个maxPos也出来
因此这个是走着脚下的，看着前方的贪心
贪心策略就是：我走着当前能走的所有位置，看到下一次能走的最远距离
那我下一次能走的最远距离就是当前区间内的最大的nums[i] + i
最后看看cur能不能到len(nums) - 1即可

ac code

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        cur, maxPos = 0, 0

        # 这一步能走的最大区间
        while cur < maxPos + 1:
            # 当前的位置，到能走的最远位置
            for i in range(cur, maxPos + 1):
                # 更新下一个的最远的位置
                maxPos = max(maxPos, nums[i] + i)
                # 如果一步步走到了最后
                if cur == len(nums) - 1:
                    return True
                # cur 和 i相对应
                cur += 1
        
        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

总结

跳跃游戏 跟 车加油游戏差不多
经典贪心