LeetCode 买卖股票的最佳时机系列题目
LeetCode上有《买卖股票的最佳时机》系列题目。其输入通常是给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第i 天的价格。
股票经营者可以通过若干次的买卖，使得自己的利益最大化。
本人在今年秋招的笔试题里做到了类似的题目，在米哈游的二面则做到了系列题目中的一道原题，故而再次深入剖析。
买卖股票的最佳时机（1）
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/
题面
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
答案
思路很简单，用一个变量记录已经出现过的最小价格。然后不断地尝试在今天卖掉。可以用动态规划，写一个 空间复杂度的 dp 数组，然而实际上不需要。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
ans = 0
lowest_price = prices[0] # 到目前为止出现过的最低价格
for price in prices:
# 如果今天比已有的最低价格高 就假装在已有的最低价格时买入 今天卖出
if price >= lowest_price:
ans = max(ans, price - lowest_price)
else:
lowest_price = price
return ans
买卖股票的最佳时机（2）
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/
题面
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
答案
思路1：贪心
因为这一题不限制交易次数，直接对每一天进行精细操作。如果今天比昨天涨了，就昨天买、今天卖。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
ans = 0
for i in range(1, len(prices)):
# 如果今天比昨天涨了 就昨天买今天卖
if prices[i] > prices[i - 1]:
ans += (prices[i] - prices[i - 1])
return ans
思路2：动态规划
- 第一维 i 表示下标为 i 的那一天（ 具有前缀性质，即考虑了之前天数的交易 ）；
- 第二维 j 表示下标为 i 的那一天是持有股票，还是持有现金。这里 0 表示持有现金（cash），1 表示持有股票（stock）。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
if n < 2:
return 0
dp = [[0, 0] for _ in range(n)]
dp[0][1] = -prices[0]
for i in range(1, n):
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
return dp[n - 1][0]
买卖股票的最佳时机（3）
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/
题面
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
答案
思路1：一遍动态规划
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
buy1 = buy2 = -prices[0]
sell1 = sell2 = 0
for i in range(1, n):
buy1 = max(buy1, -prices[i])
sell1 = max(sell1, buy1 + prices[i])
buy2 = max(buy2, sell1 - prices[i])
sell2 = max(sell2, buy2 + prices[i])
return sell2
思路2：正反各一遍动态规划
我在面试米哈游时想出来的。正序变量相当于《买卖股票的最佳时机（1）》，反序遍历相当于第二次交易。然后比较两次交易之和，即可。
买卖股票的最佳时机（4）
题面
给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
思路
动态规划
买卖股票的最佳时机（含冷冻期）
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
