代码随想录算法训练营第三十五天（贪心算法篇）| 122. 买卖股票的最佳时机, 55. 跳跃游戏，45. 跳跃游戏Ⅱ

122. 买卖股票的最佳时机

题目链接：122. 买卖股票的最佳时机 II - 力扣（LeetCode）

思路

我们要通过一次或多次的买卖股票行为达到最高利润，事实上不需要记住到底第一天买入，第几天卖出，因为利润是可以分解的。e.g. 第i天买入，第j天抛出，那么利润是price[j] - price[i] = (price[j]-price[j-1])+(price[j-1]-price[j-2])+...+ (price[i+1] - price[i])。因此，只需得到每天和前一天的利润，把所有正利润加起来即可。

代码实现

class Solution(object):
    def maxProfit(self, prices):
        diff = [prices[i+1] - prices[i] for i in range(len(prices) - 1)]
        result = sum(profit for profit in diff if profit > 0)

        return result

55. 跳跃游戏

题目链接：55. 跳跃游戏 - 力扣（LeetCode）

思路

数组num表示在位置i，最大可以跳num[i]步。把在每一步可以跳跃到的位置画出来，如果所有范围的交集可以覆盖整个数组的长度，就说明一定可以跳到最后一个位置。具体到代码，记录下每个位置能到达的最大位置，每次更新最大范围，如果范围已经超过数组的长度，就返回True。要注意每次还需要检验当前覆盖的值能不能到达当前位置。e.g.?[1,0,2,1],从位置2能跳到最后，但不能从头跳到位置2，因为在位置零最多只能跳到位置1，而从位置1不能跳到位置2。

代码实现

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        cover = 0
        if len(nums) == 1: return True
        i = 0
        # python不支持动态修改for循环中变量,使用while循环代替
        while i <= cover:
            cover = max(i + nums[i], cover)
            if cover >= len(nums) - 1: return True
            i += 1
        return False

45. 跳跃游戏Ⅱ

题目链接：45. 跳跃游戏 II - 力扣（LeetCode）

思路

本题相比上个跳跃游戏，难点在于要使用最少的跳跃次数到达数组的最后一个位置。遍历数组的每一个位置，当当前的位置到达了当前能覆盖的范围，就说明一定要再加一步。每一步都更新下次的覆盖范围，一直到走到当前范围，跳跃次数增加后，相当于续了命，之前所记录的nextDIstance就在当下为我所用，当前拥有的跳跃次数能让我们支撑到currentDistance。

代码实现

class Solution(object):
    def jump(self, nums):
        if len(nums) == 1:
            return 0
        curDistance, nextDistance = 0, 0
        ans = 0

        for i in range(len(nums)):
            nextDistance = max(i + nums[i], nextDistance)
            if i == curDistance:
                ans += 1  # 第一步（i=0)直接加1
                curDistance = nextDistance
                if curDistance >= len(nums) - 1: # 当当前范围已经能覆盖到最后了，就直接返回结果，不用再加1，以为循环刚开始就加了1.
                    break
        return ans