代码随想录算法训练营第三十二天｜122.买卖股票的最佳时机II、55. 跳跃游戏、45.跳跃游戏II

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

讲解 - 🔗

方法一：

💡这道题自己想到的办法没有解析那么清晰，大致思路就是第一步先找到第一个可以买进的时间（也就是第一个prices[i] < prices[i + 1]的i），因为只有prices[i] < prices[i + 1]才能盈利。后面就是找需要卖出的时间点：遇到prices[i] >= prices[i + 1]时，在i点卖出。。两种情况直接跳到下一个元素：

1. 已经有买入点了，又遇到了prices[i] < prices[i + 1]，此时直接跳过，因为当前i是卖出点。
2. 还没有遇到买入点，但是prices[i] >= prices[i + 1]。

但是这种方法体现不出贪心的思想。

class Solution:def maxProfit(self, prices: List[int]) -> int:res = 0in_val = Nonefor i in range(len(prices) - 1):if prices[i] < prices[i + 1] and not in_val != None:in_val = prices[i]elif prices[i] >= prices[i + 1] and in_val != None: # nums[i] >= nums[i + 1]res += prices[i] - in_valin_val = None# 两种情况直接跳到下一个元素# 1. prices[i] >= prices[i + 1] 且 in_val 为空# 2. prices[i] < prices[i + 1] 但 in_val已经有元素了，说明已经买入，要找卖出的元素# 处理最后一个元素if len(prices) >= 2 and prices[-1] > prices[-2] and in_val != None:res += prices[-1] - in_valreturn res

方法二：

💡解析的思路很清晰，计算每一天的盈利，只对正盈利相加。

此时就是把利润分解为每天为单位的维度，而不是从 0 天到第 3 天整体去考虑！

思考一下这种想法其实很有道理，没有必要一定要去找买入和卖出点。拿[1, 5, 10]举例，在第一天买入并在第三天卖出，利润为9，这种买卖方式与在第一天买入，第二天卖出并买入，在第三天卖出的利润是一样的。

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

55. 跳跃游戏 - 🔗

讲解 - 🔗
💡这道题没看解析写不出来，的确落入了惯性思维的圈套。当前位置元素如果是 2，我究竟是跳一步呢，还是两步呢？跳一步时下一步最远可以跳3步，但是跳2步下一步最远只能跳1步，越想越晕…

其实跳几步无所谓，关键在于可跳的覆盖范围！不一定非要明确一次究竟跳几步，每次取最大的跳跃步数，这个就是可以跳跃的覆盖范围。这个范围内，别管是怎么跳的，反正一定可以跳过来。
那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点！
每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。
贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。

class Solution:def canJump(self, nums: List[int]) -> bool:i = 0max_len = 0while i < len(nums) and i <= max_len:max_len = i + nums[i] if i + nums[i] > max_len else max_lenif max_len >= len(nums) - 1:return Truei += 1return False

45.跳跃游戏II - 🔗

讲解 - 🔗

💡贪心的思路，局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一。整体最优：一步尽可能多走，从而达到最少步数。

从图中可以看出来，就是移动下标达到了当前覆盖的最远距离下标时，步数就要加一，来增加覆盖距离。最后的步数就是最少步数。
这里还是有个特殊情况需要考虑，当移动下标达到了当前覆盖的最远距离下标时
如果当前覆盖最远距离下标不是是集合终点，步数就加一，还需要继续走。
如果当前覆盖最远距离下标就是是集合终点，步数不用加一，因为不能再往后走了。

class Solution:def jump(self, nums):if len(nums) == 1:return 0cur_distance = 0  # 当前覆盖最远距离下标ans = 0  # 记录走的最大步数next_distance = 0  # 下一步覆盖最远距离下标for i in range(len(nums)):next_distance = max(nums[i] + i, next_distance)  # 更新下一步覆盖最远距离下标if i == cur_distance:  # 遇到当前覆盖最远距离下标ans += 1  # 需要走下一步cur_distance = next_distance  # 更新当前覆盖最远距离下标（相当于加油了）if next_distance >= len(nums) - 1:  # 当前覆盖最远距离达到数组末尾，不用再做ans++操作，直接结束breakreturn ans