贪心算法122|55|45

122买卖股票的最佳时机II

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        result = 0
        for i in range(len(prices) - 1):
            result += max(prices[i + 1] - prices[i], 0)
        return result

55跳跃游戏

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        if len(nums) == 1:
            return True
        cover = 0
        for i in range(len(nums) - 1):
            if i <= cover:
                cover = max(cover, i + nums[i])
            if cover >= len(nums) - 1:
                return True
            
        return False

45跳跃游戏II

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