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。