LeetCode 121. 买卖股票的最佳时机：一次遍历的状态维护

买卖股票的最佳时机（LeetCode 121，Easy）表面是贪心题，实际是整个「股票系列」六道题的状态机起点：只能交易一次的版本，解法是维护历史最低价、每天计算「今天卖出」的利润——两行核心。但它的真正价值在于：这个解法可以被解读为一个极简的状态机，而股票系列的其余五题（多次交易、两次交易、带冷冻期、带手续费），全是同一个状态机的状态膨胀。本篇讲清解法本身，并立起系列的状态机框架。

解法：维护历史最低价 + 逐日算利润

问题的朴素形态：数组是每天的股价，选一天买入、之后的某一天卖出，求最大利润（必须先买后卖，无法盈利则返回 0）。暴力 O(n²)（枚举所有买卖对）显然超时。一次遍历的解法：从左到右扫，维护两个量——到昨天为止的历史最低价 min_price、至今的最大利润 best；每一天：今天的潜在利润 = prices[i] - min_price，更新 best；再用今天的股价更新 min_price。

def max_profit(prices: list[int]) -> int:
    best = 0
    min_price = float("inf")
    for p in prices:
        best = max(best, p - min_price)   # 今天卖出能拿到的最好利润
        min_price = min(min_price, p)     # 更新历史最低（含今天，明天可用）
    return best

正确性的直觉：最优交易必然是「在某天的历史最低点买入、在其后某天卖出」——遍历到每一天时，min_price 恰好是「今天之前所有可能买入点的最优」，p - min_price 恰好是「今天卖出」的最优——每一天的潜在最优都被考虑到了，全局最优自然被覆盖。一个顺序细节：先算利润再更新最低价（或更新最低价时用「≤今天」的语义），两种写法都正确——因为「同一天买卖」利润为 0，不影响答案。

状态机视角：这道题的真正框架

把这个解法重新表述成状态机，系列的门就开了。每天结束时你处于两种状态之一：持有股票（holding）或不持有（cash）。一次交易的版本：cash = 截至今天的最大利润（手里没股票），holding = 截至今天持有股票时的最优「市值-成本」状态。转移：cash = max(cash, holding + p)（今天卖出）；holding = max(holding, -p)（今天买入——持有状态的利润是负的买入价）。答案 cash。这个表述与「历史最低价」解法完全等价（holding 的最优就是 -min_price），但状态机表述的威力在于可扩展性：多次交易（122）：cash 每天都可以 max(cash, holding + p) 后再买回——贪心地「只要今天比昨天高就赚差额」，等价于收集所有上涨段（答案 = Σ max(0, p[i]-p[i-1])）；两次交易（123）：状态变成四个（第一次持有/不持有、第二次持有/不持有），转移线性链起来；带冷冻期（309）：卖出后有一天不能买（holding 的转移加一个来源）；带手续费（714）：每次交易的利润减 fee。六道题一套状态机——状态数与转移规则随题目条件膨胀，骨架从未改变。这就是本库 DP 系列反复强调的：状态机的状态设计是骨架，题目条件只是往骨架上挂状态。

贪心 vs DP：一道辨析题

「这题到底是贪心还是 DP」是常见的混淆点，值得辨析。答案：一次交易的版本，维护最低价本质上就是贪心（局部最优：在最低点买），但它恰好等价于 DP（因为只有一次交易，状态只有两个，贪心的局部最优不劣于全局）——两者的分界在「多次交易」：多次交易版本若用朴素贪心（每次都选局部最优的买卖点）会错吗？不会——因为「多次交易、无手续费」的场景下，收集所有上涨差额（贪心）恰好等价于 DP 的最优（这是本题的特殊结构：交易之间无约束成本）；但加上手续费或冷冻期后，贪心立刻失效（手续费让碎交易吃亏——必须用 DP 权衡交易次数），DP 成为唯一正确框架。辨析的结论：贪心是 DP 在特定约束下的退化形态——能贪心的条件（局部最优无损全局）需要证明；证明不了的时候，老老实实写 DP 状态机。这条辨析是本库 DP 系列的收官注脚：先 DP 保证正确，再识别可贪心的退化，是处理「贪心 or DP」类问题的标准流程。

股票六题的演进地图：一套状态机的六次变形

股票系列六道题的演进关系，值得画成一张地图总览。第一题（121）只能一次交易：两状态（holding/cash），转移各一条——本篇正文的框架。第二题（122）可以无限次交易：状态不变，转移更自由（cash 卖了随时可再买）——最优解退化为贪心（收集所有上涨差额）。第三题（123）至多两次交易：状态膨胀为四个（第一次持有/不持有、第二次持有/不持有），转移线性链（第一次的卖出解锁第二次的买入）——状态之间的顺序约束是解题核心。第四题（188）至多 k 次交易：第三题的参数化（2k 个状态循环链）——k 大于 n/2 时退化为第二题（贪心）。第五题（309）带冷冻期：卖出后有一天不能买——holding 的转移来源多一个「前天的 cash」（状态加一维或用三个状态表达「刚卖出/冷冻中/自由」）。第六题（714）带手续费：每笔交易扣固定费用——cash 的转移减去 fee（手续费改变了「卖出的净利润」，交易次数的权衡因此自动内生化）。六题一张表的读法：状态数从 2 到 2k+1，转移规则随约束微调——六道题是一次「状态机设计」的完整课程：先立两状态骨架，然后按约束逐个加状态、加规则——学会「把约束翻译成状态与转移」，比背六道题的代码有用十倍。

股票系列的状态机图：一张图记住六道题

股票六题的状态机，可以画成一张统一的状态转移图记住全部。图的节点：按「交易次数的已用数 × 持有状态」编号——121 是 (0,未持有)→(0,持有)→(1,未持有) 的三节点链；123/188 是 (已交易次数, 持有状态) 的二维网格状状态图；309 在卖出后插入「冷冻」节点；714 在每次「卖出」的转移上挂一个减 fee 的权重。一张图的读法：节点 = 你在某个交易日收盘时的处境；边 = 你的一个决策（买/卖/不动）——最优解就是图上从起点到终点的最长路（利润最大）——所有的股票题都是「在这张状态图上找最长路」的同一个问题的不同图。记忆锚点的最后压缩：121 两个状态、122 两个状态自由转移、123 四个状态链、188 2k 个状态环、309 三个状态（含冷冻）、714 两个状态带负权边——六个数字，一套框架，全系列的复习成本压缩到一分钟。

状态机的「不可达状态」清理：DP 优化的隐藏红利

股票系列的状态机框架有一个常被忽略的优化红利：不可达状态的清理。以两次交易的版本（LeetCode 123）为例，四个状态的转移链是「第一次买入→第一次卖出→第二次买入→第二次卖出」——但交易次数上限为 k 时，某些状态在某些天数是不可能的（第 1 天不可能已经完成两次交易）。识别并清理这些不可达状态，可以减少无效的转移计算——具体的清理方法：从第 1 天开始逐天标记可达状态，不可达状态跳过转移计算。这个优化的更一般意义：DP 的状态空间中经常存在「结构性不可达」的状态（由问题的约束决定）——清理它们不是微优化，是对问题结构的深入理解——不可达状态的识别往往揭示新的约束或简化转移的条件。把「不可达状态清理」作为 DP 优化清单的一项，是 DP 工程化的最后一块拼图。

状态机的通用性：从股票到一切序列决策

股票系列的状态机框架是一切序列上决策问题的通用框架：每个时间步做一个决策，决策影响下一时间步的可用状态。同构的问题：背包问题（每个物品拿或不拿——状态是容量与已选物品）、编辑距离（每个字符匹配替换或删除——状态是两个序列的位置）、爬楼梯（每次上一步或上两步——状态是当前位置）——它们的共同骨架：状态定义加转移方程加边界加遍历顺序。框架的判断清单：问题是否可以分解为逐步决策？决策是否影响下一步的可用选项？状态空间是否有限？三问都是是则状态机 DP 就是正确的框架。学完股票系列的终极收获：状态机思维不是一种特定的算法，是一种把序列决策问题结构化的思维方式——掌握了它一切每天做一个选择类的问题都有了统一的解题入口。

小结

这篇收成四条：一次遍历解法——维护历史最低价，每天算「今天卖出」的利润，正确性来自「最优交易必然从历史最低点买出」；状态机视角是这个解法的真正框架——cash 与 holding 两状态，六道股票题是同一状态机的状态膨胀（多次交易、两次、冷冻期、手续费）；贪心与 DP 的辨析——一次交易时两者等价，多次交易无手续费时贪心恰好成立，加了手续费或冷冻期后贪心失效必须 DP；流程纪律——先 DP 保证正确，再识别可贪心的退化。股票系列的入口已开，状态机的骨架已立——剩下的五道变体，是这套框架的练手题。

参考资料

LeetCode 121. Best Time to Buy and Sell Stock —— 题目与官方题解；122/123/309/714 为系列变体
本库前篇：《LeetCode 53. 最大子数组和：Kadane 算法的一步之遥》《LeetCode 198. 打家劫舍》—— 状态维护遍历的邻居题
LeetCode 系列题解的状态机统一表述（社区经典整理）