LeetCode 121-188 股票买卖最佳时机系列题解，如何一网打尽？

题目链接： 121. 买卖股票的最佳时机 122. 买卖股票的最佳时机 II 123. 买卖股票的最佳时机 III 188. 买卖股票的最佳时机 IV 目录核心概念：状态定义1. 121. 买卖股票的最佳时机 (限制 1 笔交易)解法一：贪心算法 (最优解)解法二：动态规划 (通用框架简化版)2. 122. 买卖股票的最佳时机 II (不限交易次数)解法一：贪心算法 (最优解)解法二：动态规划3. 123. 买卖股票的最佳时机 III (最多 2 笔交易)解法：动态规划 (4 个状态变量)4. 188. 买卖股票的最佳时机 IV (最多 k 笔交易)解法：通用动态规划总结与通用框架通用 DP 状态转移方程学习建议 这一组题目是动态规划（Dynamic Programming）和贪心算法（Greedy Algorithm）的经典入门系列。它们的核心区别在于交易次数限制的不同。 本博客将按照从简单到复杂的顺序，逐一讲解每道题的核心思路、多种解法，并提供带有详细注释的 Python 3 代码。 核心概念：状态定义 在解决这类问题时，我们通常关注两个核心状态： 持有股票 (Hold)：当前手里有一只股票。 不持有股票 (Cash)：当前手里没有股票（持有现金）。 我们的目标是在最后一天，处于不持有股票的状态下，使手中的现金（利润）最大化。 1. 121. 买卖股票的最佳时机 (限制 1 笔交易) 题目含义： 我们只能买入一次，卖出一次。求最大利润。如果无法获利，返回 0。 解法一：贪心算法 (最优解) 思路： 我们要找 卖出价 - 买入价 的最大值，且卖出必须在买入之后。 我们可以遍历每一天的价格，维护一个历史最低价格 (min_price)。 对于每一天的价格，我们计算：如果今天卖出，利润是多少？ 即 当前价格 - 历史最低价格。 不断更新最大利润即可。 复杂度： 时间：O(N)，只需遍历一次。 空间：O(1)，只需几个变量。 from typing import List class Solution: def maxProfit(self, prices: List[int]) -> int: # 初始化历史最低价格为一个极大的数 min_price = float('inf') # 初始化最大利润为 0 max_profit = 0 for price in prices: # 1. 更新历史最低价格：看看今天是不是比之前更便宜 if price < min_price: min_price = price # 2. 计算如果今天卖出的利润，并更新最大利润 # 注意：即使今天价格很低，price - min_price 也是 0，不会更新 max_profit elif price - min_price > max_profit: max_profit = price - min_price return max_profit 解法二：动态规划 (通用框架简化版) 思路： 定义两个状态变量： cash: 第 i 天结束时，不持有股票的最大利润。 hold: 第 i 天结束时，持有股票的最大利润。 状态转移： cash = max(昨天就不持有，昨天持有今天卖出) hold = max(昨天就持有，昨天不持有今天买入) 因为只能交易 1 次，买入时的利润基础是 0。 class Solution: def maxProfit(self, prices: List[int]) -> int: if not prices: return 0 # 初始化： # cash: 第 0 天不持有，利润为 0 # hold: 第 0 天持有，利润为 -prices[0] (花钱买了) cash = 0 hold = -prices[0] for i in range(1, len(prices)): # 今天不持有 = max(昨天就不持有，昨天持有 + 今天卖出) cash = max(cash, hold + prices[i]) # 今天持有 = max(昨天就持有，今天买入) # 注意：因为只能买 1 次，所以今天买入的基础利润是 0，即 -prices[i] hold = max(hold, -prices[i]) return cash 2. 122. 买卖股票的最佳时机 II (不限交易次数) 题目含义： 我们可以买卖无数次，但同一时间最多持有一股。求最大利润。 解法一：贪心算法 (最优解) 思路： 既然不限次数，我们可以吃掉所有的上涨波段。 只要明天的价格比今天高，我们就今天买、明天卖。 这等价于：累加所有 prices[i] - prices[i-1] > 0 的差值。 例子：价格 [1, 3, 5]。 1 买 5 卖，利润 4。 1 买 3 卖 (利润 2) + 3 买 5 卖 (利润 2) = 4。 结果一样，但分段计算更简单。 class Solution: def maxProfit(self, prices: List[int]) -> int: total_profit = 0 # 从第 2 天开始遍历，对比前一天 for i in range(1, len(prices)): # 如果今天比昨天贵，就昨天买今天卖，赚取差价 if prices[i] > prices[i - 1]: total_profit += prices[i] - prices[i - 1] return total_profit 解法二：动态规划 思路： 与 121 题类似，但区别在于：今天买入时，之前的利润基础不是 0，而是昨天不持有股票时的利润 (cash)。 因为可以交易无数次，之前的利润可以累积。 class Solution: def maxProfit(self, prices: List[int]) -> int: if not prices: return 0 cash = 0 # 不持有股票的最大利润 hold = -prices[0] # 持有股票的最大利润 for i in range(1, len(prices)): # 保存昨天的 cash，因为计算 hold 时需要用到昨天的状态 prev_cash = cash # 今天不持有 = max(昨天不持有，昨天持有 + 今天卖出) cash = max(cash, hold + prices[i]) # 今天持有 = max(昨天持有，昨天不持有 - 今天买入) # 注意这里：买入时的本金是 prev_cash，因为可以多次交易 hold = max(hold, prev_cash - prices[i]) return cash 3. 123. 买卖股票的最佳时机 III (最多 2 笔交易) 题目含义： 最多买卖两次。不能同时参与多笔交易（必须先卖再买）。 解法：动态规划 (4 个状态变量) 思路： 因为最多 2 笔，我们可以把过程拆分为 4 个状态： 第一次买入后 (buy1)：持有第 1 股。 第一次卖出后 (sell1)：完成第 1 笔交易，不持股。 第二次买入后 (buy2)：持有第 2 股。 第二次卖出后 (sell2)：完成第 2 笔交易，不持股。 我们需要在遍历过程中不断更新这 4 个状态的最大值。 初始化技巧： buy 状态初始化为负无穷大 (-float('inf'))，表示初始时不可能持有股票。 sell 状态初始化为 0。 class Solution: def maxProfit(self, prices: List[int]) -> int: if not prices: return 0 # 初始化四个状态 # buy1: 第一次买入后的最大利润 (初始为负无穷，表示未发生) buy1 = -float('inf') # sell1: 第一次卖出后的最大利润 sell1 = 0 # buy2: 第二次买入后的最大利润 buy2 = -float('inf') # sell2: 第二次卖出后的最大利润 sell2 = 0 for price in prices: # 更新第一次买入：要么保持之前的买入状态，要么今天第一次买入 (0 - price) buy1 = max(buy1, -price) # 更新第一次卖出：要么保持之前卖出状态，要么今天卖出第一次买入的股票 sell1 = max(sell1, buy1 + price) # 更新第二次买入：要么保持之前买入状态，要么用第一次卖出的利润今天买入 buy2 = max(buy2, sell1 - price) # 更新第二次卖出：要么保持之前卖出状态，要么今天卖出第二次买入的股票 sell2 = max(sell2, buy2 + price) # 最终结果一定是卖出了股票（不持有），所以返回 sell2 # 注意：如果只交易 1 次更优，sell2 也会包含这种情况（因为 buy2 可以选择不买） return sell2 4. 188. 买卖股票的最佳时机 IV (最多 k 笔交易) 题目含义： 这是最通用的版本，最多允许 k 次交易。 解法：通用动态规划 思路： 这是 123 题的推广。我们需要一个数组来记录 k 次交易的状态。 定义 dp[j][0] 和 dp[j][1]： dp[j][0]: 完成 j 次交易后，不持有股票的最大利润。 dp[j][1]: 完成 j-1 次交易，正在进行第 j 次交易（持有股票）的最大利润。 重要优化： 如果 k 非常大（例如 k >= 天数/2），这就相当于没有限制交易次数。此时直接退化为 122 题 的解法。这可以避免不必要的计算和内存开销。 class Solution: def maxProfit(self, k: int, prices: List[int]) -> int: if not prices: return 0 n = len(prices) # 优化：如果 k 很大，相当于可以无限次交易，直接使用 122 题的贪心解法 # 因为最多有效交易次数不会超过天数的一半（一天买一天卖） if k >= n // 2: profit = 0 for i in range(1, n): if prices[i] > prices[i - 1]: profit += prices[i] - prices[i - 1] return profit # 初始化 DP 数组 # dp[j][0] 表示第 j 笔交易卖出后（不持股）的最大利润 # dp[j][1] 表示第 j 笔交易买入后（持股）的最大利润 # 大小为 k+1，因为交易次数从 1 到 k dp = [[0] * 2 for _ in range(k + 1)] # 初始化持有状态为负无穷，因为还没开始交易不可能持有股票 for j in range(1, k + 1): dp[j][1] = -float('inf') # 但是 dp[0][1] 代表第 0 笔交易（没交易），所以还是 0？ # 主要是后面的 dp[j][1] = max(dp[j][1], dp[j - 1][0] - price) 依赖于 dp[0][1] # 遍历每一天的价格 for price in prices: # 遍历每一笔交易次数 (从 1 到 k) # 注意：这里可以从 1 到 k 正序遍历，因为当天的卖出依赖于当天的买入（同一天买卖利润为 0，不影响结果） # 但为了逻辑严谨（依赖前一天的状态），通常理解为基于上一轮循环的值 for j in range(1, k + 1): # 状态 0 (不持股)：要么昨天就不持股，要么昨天持股今天卖了 dp[j][0] = max(dp[j][0], dp[j][1] + price) # 状态 1 (持股)：要么昨天就持股，要么昨天不持股（完成了 j-1 笔）今天买了 # 依赖的是 dp[j-1][0]，即上一笔交易完成后的利润 dp[j][1] = max(dp[j][1], dp[j - 1][0] - price) # 返回完成 k 笔交易后不持股的最大利润 return dp[k][0] 总结与通用框架 这四道题其实是一个问题的不同约束条件。我们可以用一个统一的状态机视角来看待： 题目 交易次数限制 核心解法 关键变量 121 1 次 贪心 / DP min_price, max_profit 122 无限次 贪心 (累加正差) sum(prices[i] - prices[i-1]) 123 2 次 DP (4 个变量) buy1, sell1, buy2, sell2 188 k 次 DP (数组) dp[k][2] 通用 DP 状态转移方程 对于第 i 天，最多允许 k 次交易： dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]) (今天不持有 = max(昨天不持有，昨天持有 + 今天卖出)) dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]) (今天持有 = max(昨天持有，昨天不持有 + 今天买入)) 121 题 是 k=1 的特例。 122 题 是 k=∞ 的特例（此时 k 和 k-1 没区别，可消去 k 维度）。 123 题 是 k=2 的特例（可将数组展开为 4 个变量）。 188 题 是通用解。 学习建议 先彻底理解 121 题 的“最低点买入”逻辑。 再理解 122 题 的“只要有利润就赚”逻辑。 最后通过 188 题 的代码框架，理解如何用代码表达“持有”和“不持有”的状态切换。 面试中如果遇到此类问题，先问清楚交易次数限制和是否有冷却期（如 309 题），然后套用上述框架。