代码随想录｜Day27｜贪心02｜122.买卖股票的最佳时机II、55.跳跃游戏、45.跳跃游戏II

122.买卖股票的最佳时机II

本题可以将最终利润分解为每日利润：

假如第 0 天买入，第 3 天卖出，那么利润为：prices[3] - prices[0]。

相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。

如下图所示，最大利润这样获得：第二天买，第四天卖，第五天买，第六天卖。要实现最大利润，可以每天都进行买卖，只收集正利润的天数。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        profit = 0

        for i in range(1, len(prices)):
            if prices[i] > prices[i-1]:
                profit += prices[i] - prices[i-1]

        return profit

55.跳跃游戏

遍历数组，我们维护一个 最大范围，只要最大范围能过覆盖到数组末位，则说明可以到达最后一个位置。

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

        n = len(nums)
        cover = 0

        for i in range(n):
            # 更新范围的前提是，我只能在上一个范围中取新的范围
            if i <= cover:
                cover = max(cover, i + nums[i])
                if cover >= n - 1:
                    return True

        return False

45.跳跃游戏II

本题和 55.跳跃游戏 的区别是一定可以跳跃到末尾，但需要计算最少跳跃步数。

思路：同样是计算每一步的覆盖范围，在此覆盖范围内，如果无法到达末尾，则需要启用下一个范围，并且是最大范围（因为我们寻找最少跳跃步数）跳跃数+1。

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

        if len(nums) == 1:
            return 0

        jumps = 0
        currentCover = 0
        nextCover = 0

        for i in range(len(nums)):
            # 最少跳跃次数，维护一个最大覆盖范围
            nextCover = max(nextCover, i + nums[i])
            # 如果当前范围内无法到达，则跳一步到下一个范围
            if i == currentCover:
                jumps += 1
                currentCover = nextCover
                if currentCover >= len(nums) - 1:
                    break

        return jumps