C++实现LeetCode(309.买股票的最佳时间含冷冻期)

前言LeetCode 309 是股票买卖系列里状态最多的一题允许多次买卖但卖出股票的第二天不能买入也就是有一天的冷冻期。求能获得的最大利润。题目通常给出一个整数数组pricesprices[i]表示第i天的股价。这题的难点不在代码长度而在状态定义持有股票、当天卖出、冷冻期、正常不持有这几种状态之间的转移容易混淆。常见的错误包括把“卖出后第二天不能买”写成“卖出当天不能买”用sold[0] 0初始化凭空得到一笔卖出收益把买入的来源写成前一天卖出导致冷冻期被跳过最后返回持有股票的状态以及滚动变量更新时用已覆盖的旧值计算新值。本文以 C17 为准用三个状态建立动态规划hold持有股票、sold当天刚卖出、rest不持有且不在冷冻期。先写二维版本说明转移再压缩成常数空间。所有推导都是按状态定义手工进行的不涉及运行结果。一、状态定义把第i天结束时的状态分为三类状态含义当天结束时的现金hold手里持有股票买入花费后的现金可能为负sold当天卖出了股票卖出后的现金rest不持有股票且不处于“刚卖出”的冷冻期现金这里的“现金”只计算交易带来的盈亏初始为 0。买入时减去股价卖出时加上股价。为什么需要sold和rest两个“不持有”状态因为冷冻期的限制只作用于“刚卖出的下一天”。如果把所有不持有状态合并成一个就无法区分“昨天刚卖今天不能买”和“已经空仓一段时间今天可以买”。状态转移持有要么昨天就持有今天不动要么今天买入。今天能买入的前提是昨天处于rest不持有且不在冷冻期。所以hold[i] max(hold[i-1], rest[i-1] - prices[i])。当天卖出昨天必须持有今天按prices[i]卖出sold[i] hold[i-1] prices[i]。空仓休息要么昨天就已经在休息要么昨天刚卖出今天进入冷冻期rest[i] max(rest[i-1], sold[i-1])。注意hold的买入来源是rest[i-1]不是sold[i-1]。如果第i-1天卖出第i天是冷冻期不能买入而rest[i]的转移允许sold[i-1]进入休息状态到第i1天才能从rest[i]买入。这正是“卖后隔一天才能买”的体现。二、初始化与答案第 0 天买入hold[0] -prices[0]卖出第 0 天不可能卖出没有前一天持仓应设为负无穷休息rest[0] 0表示什么都没做。sold[0]不能设为 0。设为 0 相当于“第 0 天无成本卖出得到 0 元”后续可能被错误地当成有效收益甚至让答案虚高。用INT_MIN或足够小的负数表示不可达。最终答案是max(sold[n-1], rest[n-1])不能是hold[n-1]。最后一天还持有股票说明没有卖出收益尚未兑现题目要求的是完成交易后的最大利润。sold和rest都表示不持有取两者较大值即可。若prices为空利润为 0若只有一个元素无法完成一次买卖利润也是 0。这两种情况要在代码入口处理。三、二维 DP 写法先写出完整表格版本便于核对状态// 适用于 C17#include algorithm#include limits#include vectorint max_profit_2d(const std::vectorint prices){const int n static_castint(prices.size());if (n 2)return 0;const long long NEG std::numeric_limitslong long::min() / 2;std::vectorlong long hold(n, NEG);std::vectorlong long sold(n, NEG);std::vectorlong long rest(n, 0);hold[0] -prices[0];for (int i 1; i n; i){hold[i] std::max(hold[i - 1], rest[i - 1] - prices[i]);sold[i] hold[i - 1] prices[i];rest[i] std::max(rest[i - 1], sold[i - 1]);}return static_castint(std::max(sold[n - 1], rest[n - 1]));}NEG取long long最小值的一半是为了在sold[i] hold[i-1] prices[i]中避免溢出。实际上hold[i-1]从第 1 天起就已是有效值要么是-prices[0]要么是买入后的现金不会用到NEG但保留这个保护不影响正确性。用题目常见的例子prices [1, 2, 3, 0, 2]手工推演天数 i价格holdsoldrest01-1不可达012-11023-121301-1242132第 4 天结束时sold 3、rest 2答案是 3。交易过程可以是第 0 天买、第 2 天卖赚 2冷冻第 3 天第 3 天买、第 4 天卖赚 2总利润 4这里要小心第 2 天卖出后第 3 天是冷冻期不能买入。因此上面的 3 对应的交易是第 0 天买、第 1 天卖赚 1第 2 天买、第 4 天卖第 2 天卖出后第 3 天冷冻不能第 2 天买。让我按状态回溯第 4 天sold hold[3] 2 1 2 3hold[3] 1来自rest[2] - 0 1 - 0 1即第 2 天休息后第 3 天以 0 买入rest[2] 1来自sold[1] 1即第 1 天卖出。第 1 天的卖出来自第 0 天买入-1 2 1。所以交易是第 0 天买、第 1 天卖1第 2 天冷冻第 3 天买、第 4 天卖2总计 3。正确。第 2 天卖出再第 3 天买是违反冷冻期的手工推演时正好能暴露这种错误理解。这个例子说明冷冻期是“卖出后的下一个交易日”不是“卖出当天”。第 1 天卖出第 2 天不能买第 2 天休息第 3 天才能买。四、滚动变量常数空间二维表只依赖前一天因此可以用三个变量滚动// 适用于 C17#include algorithm#include limits#include vectorint max_profit(const std::vectorint prices){if (prices.size() 2)return 0;const long long NEG std::numeric_limitslong long::min() / 2;long long hold -prices[0];long long sold NEG;long long rest 0;for (std::size_t i 1; i prices.size(); i){const long long price prices[i];const long long next_hold std::max(hold, rest - price);const long long next_sold hold price;const long long next_rest std::max(rest, sold);hold next_hold;sold next_sold;rest next_rest;}return static_castint(std::max(sold, rest));}三个next_临时变量必须全部算完再统一赋值。如果写成hold std::max(hold, rest - price);sold hold price; // 错误hold 已被更新rest std::max(rest, sold); // 错误sold 已被更新那么sold会用到“今天已经买入后的 hold”相当于同一天既买又卖rest也会用到今天的sold冷冻期被压缩。这类错误在滚动数组里很常见根源是没有区分“前一天的状态”和“今天的状态”。时间复杂度和空间复杂度都是O(n)时间和O(1)额外空间不计输入。五、另一种等价写法也可以用两个数组hold和cash其中cash[i]表示第i天结束时不持有股票的现金买入时要求从前两天的不持有状态转移// 适用于 C17int max_profit_alt(const std::vectorint prices){const int n static_castint(prices.size());if (n 2)return 0;std::vectorint hold(n, 0);std::vectorint cash(n, 0);hold[0] -prices[0];cash[0] 0;for (int i 1; i n; i){hold[i] std::max(hold[i - 1], (i 2 ? cash[i - 2] : 0) - prices[i]);cash[i] std::max(cash[i - 1], hold[i - 1] prices[i]);}return cash[n - 1];}这里cash[i-2]的含义是如果第i-1天卖出第i天处于冷冻期不能用cash[i-1]买入只能用第i-2天结束时的现金。i 2时第 0 天或第 1 天买入都不受冷冻期限制用初始现金 0。两种写法等价但三状态版本把“冷冻期”显式建模转移条件的含义更直观两状态版本更短但i 2的下标容易写错。面试或刷题时选一种自己能手推清楚的即可不要在两种记法之间来回切换。六、边界与变体需要检查的边界prices为空返回 0不能访问prices[0]只有一个价格无法完成买卖返回 0价格全部下跌最优是不交易答案为 0价格全部相同不交易答案为 0冷冻期跨过数组末尾最后一天卖出后没有后续买入答案仍按sold计算不需要额外处理。股票系列题容易混淆变体题目约束状态差异121只能买卖一次维护最小价格或单次持有状态122可多次买卖无冷冻期持有/不持有两状态卖出后可立即买309可多次买卖卖后冷冻一天需要区分“刚卖出”和“休息”714可多次买卖有手续费卖出时减去手续费188最多 k 次交易增加交易次数维度把 309 的rest状态去掉、允许sold[i-1]直接买入就退化成 122在卖出时减去fee就得到 714 的无冷冻期版本。理解状态机后这些变体只是在转移式上增减项。常见坑点❌ 把sold[0]初始化为 0。✅ 第 0 天不可能卖出应设为负无穷否则会凭空产生收益污染后续转移。❌ 买入来源写成sold[i-1] - prices[i]。✅ 卖出后第二天不能买买入只能来自rest[i-1]sold[i-1]要到rest[i]才可用。❌ 把冷冻期理解为“卖出当天不能买”。✅ 卖出当天本来就不能同时买限制的是卖出后的下一个交易日即第i天卖出第i1天不能买。❌ 最终返回hold[n-1]。✅ 返回max(sold[n-1], rest[n-1])持有股票意味着尚未卖出利润没有兑现。❌ 滚动更新时先改hold再算sold用了今天的状态。✅ 先把next_hold、next_sold、next_rest都算出来再统一赋值。❌ 用int存负无穷并直接加价格导致溢出。✅ 用足够小的负数如INT_MIN / 2或long long避免加法溢出。❌ 忘记处理空数组或单元素数组访问prices[0]越界。✅ 入口处判断prices.size() 2直接返回 0。❌ 把 309 的转移直接套到 122无冷冻期答案偏小。✅ 先确认题目约束无冷冻期时卖出后可以立即买入不需要rest的延迟。总结项目内容状态hold持有、sold当天卖出、rest空仓休息持有转移max(hold, rest - price)卖出转移hold price休息转移max(rest, sold)初始值hold -prices[0]sold 负无穷rest 0答案max(sold, rest)时间/空间O(n)/O(1)309 的关键是把“冷冻期”建模成一个独立状态而不是在买入时临时判断。sold表示“今天刚卖明天不能买”rest表示“已经空仓随时可买”两者分开后转移式自然满足“卖后隔一天”的约束。写完后用[1,2,3,0,2]这类包含下跌和反弹的例子手工推演一遍重点检查买入来源和滚动变量的更新顺序基本就能排除大多数错误。