买卖股票的最佳时机问题在 LeetCode 上是一整个系列从编号 121 一路到 714我在准备 C 后端岗面试时前前后后刷了两遍。第一遍是每题单独用贪心或暴力打补丁第二遍才真正意识到这个系列考的不是买卖逻辑而是你懂不懂状态机 DP、滚动数组、以及 C 里那些和数组初始化相关的隐蔽坑。这篇文章把我自己的推导路径、踩过的坑、以及沉淀下来的一套通用模板完整记录下来适合正在刷算法题、准备 C 岗位笔试面试的读者参考。1. 从 121 出发这道简单题到底在考什么121 的题目描述很短给定一个数组pricesprices[i]表示第 i 天的股票价格你只能选择某一天买入并在之后的某一天卖出设计一个算法返回能获得的最大利润。如果没有利润返回 0。很多人在这一题上选择暴力两层循环。外层枚举买入日内层枚举卖出日维护最大差值。代码确实能过但面试官接下来大概率会问你时间复杂度能不能降这时候如果你能给出 O(n) 的贪心解法并且说明白它和动态规划之间的关系这道简单题才算真正过关。1.1 暴力解法的代价O(n²) 为什么不能接受暴力写出来很直白但n一旦到 10^5 量级10^10 次运算在 C 里也要跑几十秒。力扣的测试数据虽然不一定卡到那么大但面试场景下复杂度分析是必问项。我第一遍刷的时候就用暴力AC 之后自我感觉良好后来在模拟面试中被问到如果 n 是 10^6 呢才意识到自己根本没抓住重点。暴力版本可以参考如下逻辑int maxProfit(vectorint prices) { int n prices.size(), ans 0; for (int i 0; i n; i) { for (int j i 1; j n; j) { ans max(ans, prices[j] - prices[i]); } } return ans; }这个解法的问题在于买入日的枚举是完全冗余的。对于任意一个卖出日 j最优的买入日必然是 0 到 j-1 天中价格最低的那一天。于是我们可以把买入日在卖出日之前这个约束变成边遍历边维护历史最低价。1.2 贪心解法维护历史最低价的 O(n) 写法用minPrice记录当前遍历到的最低价用maxProfit记录当前能得到的最大利润。每天先尝试用今天的价格减去历史最低价更新利润再用今天价格更新最低价。顺序很关键先卖后买因为不能先卖再买。int maxProfit(vectorint prices) { int minPrice INT_MAX; int maxProfit 0; for (int price : prices) { maxProfit max(maxProfit, price - minPrice); minPrice min(minPrice, price); } return maxProfit; }如果数组为空或只有一个元素minPrice保持INT_MAXmaxProfit为 0结果正确。这个解法我建议背熟因为它是整个系列里唯一一个真正意义上的简单题解后续所有变体都会在它基础上加约束。但这里我想多说一句不要只记住代码。面试官如果追问为什么price - minPrice一定对应一次合法交易你要能说清楚——因为minPrice是在当前天之前出现的所以买入日期必然早于卖出日期。这个约束就是股票问题比一般求最大差值多出来的那层意思。2. 六道题共用的状态机把交易问题变成一张二维表刷到 309、188 这些题时如果还靠拍脑袋找规律会非常累。我的转折点是把 121 到 714 的六道题放在一起看发现它们都能用同一个状态机模型描述。通用状态定义是dp[i][k][0] 表示第 i 天结束时最多完成 k 笔交易且当前不持有股票的最大利润 dp[i][k][1] 表示第 i 天结束时最多完成 k 笔交易且当前持有股票的最大利润把i看成天数下标k看成已经用掉的交易次数第三维 0/1 表示持仓状态。这三个维度对应了股票问题里的三个约束时间顺序、次数限制、持仓状态。理解了这个三维坐标系六道题就都是它的投影或者特例。2.1 状态转移方程为什么要这样写每一天的决策只有三件事买入、卖出、什么都不做。基于这个事实转移方程是固定的dp[i][k][0] max(dp[i-1][k][0], dp[i-1][k][1] prices[i]) dp[i][k][1] max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])第一行含义今天不持有股票要么昨天就不持有且今天没操作要么昨天持有且今天卖出。卖出会增加利润prices[i]。第二行含义今天持有股票要么昨天就持有且今天没操作要么昨天不持有且今天买入。买入会减少利润prices[i]同时把交易次数k消耗掉一次。注意这里有一个行业约定在买入时扣除交易次数。另一种等价做法是在卖出时扣后面我会单独说这一点因为它会直接影响答案下标。2.2 为什么初始化要格外小心状态转移中有减法dp[i-1][k-1][0] - prices[i]如果dp数组初始化为 0k较小时会出现凭空买入的漏洞导致结果偏大。所以dp[i][k][1]的初始值必须是一个足够小的负数表示不可能持有。C 里我习惯用INT_MIN / 2。不要直接用INT_MIN因为在INT_MIN - prices[i]这样的运算中会溢出无符号溢出是回绕有符号溢出是未定义行为哪怕本地能跑出正确结果换台机器或换份数据也可能翻车。vectorvectorint dp(n, vectorint(k 1, vectorint(2, 0))); for (int i 0; i n; i) { for (int j 0; j k; j) { dp[i][j][1] INT_MIN / 2; } }这里只初始化[1]状态还不够还要注意第 0 天的边界。第 0 天如果买入利润是-prices[0]对应dp[0][1][1] -prices[0]其余延续负数初始值。2.3 三维数组在 C 里的表达方式我在代码里通常用一个嵌套 vector 表达三维状态但面试时更推荐用两个二维数组滚动更新因为空间复杂度可以从 O(nk) 降到 O(k)。后面讲 188 时会给出滚动数组代码。另外一个容易忽略的细节是vectorvectorvectorint的构造方式写起来非常啰嗦而且逐层初始化的默认值很容易设错。我建议写一个辅助 lambda 或者直接拆分维度减少出错的概率。3. 先松后紧121 / 122 / 309 的三个递进实现这一节我按约束从弱到强的顺序讲。先是不限次数再加冷冻期让读者体会状态数是怎么一步一步变多的。3.1 121 套用状态机两个变量就是二维状态的压缩121 要求最多一次交易所以k只能是 0 或 1。我们其实可以把两个三维状态压缩成两个整数hold表示当前持有股票的最大利润sold表示当前不持有股票的最大利润。int maxProfit(vectorint prices) { if (prices.empty()) return 0; int hold -prices[0]; int sold 0; for (int i 1; i (int)prices.size(); i) { int prevSold sold; int prevHold hold; sold max(prevSold, prevHold prices[i]); hold max(prevHold, 0 - prices[i]); } return sold; }注意hold转移中用的是0 - prices[i]代表第一次买入而不是sold - prices[i]。因为只允许一次交易买入之前必然没有卖出过。这里用sold就会错误地允许卖出后再买入从而变成 122 的语义。3.2 122 不限次数贪心和状态机是两种视角122 允许无限次交易但同一时刻只能持有一支股票。这题最经典的解法是贪心只要今天的价格比昨天高就认为昨天买入、今天卖出能产生利润累加所有正差价。int maxProfit(vectorint prices) { int ans 0; for (int i 1; i (int)prices.size(); i) { if (prices[i] prices[i - 1]) { ans prices[i] - prices[i - 1]; } } return ans; }为什么可以这样贪因为不限交易次数时每一段上涨都可以单独构成一次交易相邻上涨差价累加等价于在最低点买入、最高点卖出。比如价格序列 1, 2, 3只做一次交易利润是 2拆成 1 买 2 卖、2 买 3 卖累加也是 2。这个等价性只在没有交易手续费时成立到 714 就会变味后面细说。用状态机写 122 时因为 k 无限状态只剩下hold和soldint maxProfit(vectorint prices) { int hold INT_MIN / 2; int sold 0; for (int price : prices) { int prevHold hold; int prevSold sold; sold max(prevSold, prevHold price); hold max(prevHold, prevSold - price); } return sold; }对比 121 的版本唯一的区别是hold可以从prevSold - price转移过来即允许卖出之后再次买入。3.3 309 冷冻期从二状态变成三状态309 在 122 基础上加了限制卖出股票的第二天不能买入也就是冷冻期为 1 天。此时不持有这个状态必须拆成两个sold表示今天不持有且不在冷冻期cool表示今天处于冷冻期今天刚卖出。状态转移变成sold max(prevSold, prevCool) cool prevHold price hold max(prevHold, prevSold - price)我用屋顶一句话概括sold是能自由买入的空白期cool是卖出后被迫休息的状态买入只能从sold发生。实现时注意cool转移用的是昨天hold所以每天要先保存昨天三个状态再更新。int maxProfit(vectorint prices) { int hold INT_MIN / 2; int sold 0; int cool 0; for (int price : prices) { int prevHold hold; int prevSold sold; int prevCool cool; sold max(prevSold, prevCool); cool prevHold price; hold max(prevHold, prevSold - price); } return max(sold, cool); }这里有一个小细节答案是max(sold, cool)因为交易结束时可能刚好处于卖出后的冷冻期而cool也可能携带最终利润。面试时容易漏掉建议写完之后用[1,2,3,0,2]这个经典用例跑一遍。4. 限制交易次数的重头戏123 与 188 的滚动数组写法如果说前面几题是在考状态划分那 123 和 188 就是在考你对交易次数维度的掌握程度。4.1 123只有两次交易时四个变量依次滚动交易次数上限是 2所以只需要维护k1和k2两组状态。常见的面试写法是不建二维数组直接用四个变量int maxProfit(vectorint prices) { int buy1 INT_MIN / 2, sell1 0; int buy2 INT_MIN / 2, sell2 0; for (int price : prices) { buy1 max(buy1, -price); sell1 max(sell1, buy1 price); buy2 max(buy2, sell1 - price); sell2 max(sell2, buy2 price); } return sell2; }这里的顺序是精心设计的buy1 - sell1 - buy2 - sell2它在同一个循环里把昨天的状态自然变成了今天的状态。为什么允许这样顺序更新因为buy2引用的是刚更新过的sell1这等价于昨天的 sell1 和今天的 sell1 取最优而第二种交易完全可以基于今天已完成的第一笔交易结果来决策这种重叠在同一时间点完成是允许的。4.2 188把 2 换成 k滚动数组才开始发力当k变成参数就不能手写四个变量了。常规解法是int maxProfit(int k, vectorint prices) { int n prices.size(); if (n 2 || k 0) return 0; if (k n / 2) { // 交易次数足够多等价于无限次交易 int ans 0; for (int i 1; i n; i) { if (prices[i] prices[i - 1]) ans prices[i] - prices[i - 1]; } return ans; } vectorint sold(k 1, 0); vectorint hold(k 1, INT_MIN / 2); for (int price : prices) { for (int j k; j 1; --j) { sold[j] max(sold[j], hold[j] price); hold[j] max(hold[j], sold[j - 1] - price); } } return sold[k]; }两个关键点第一k n / 2时直接走贪心。因为一次完整的买卖至少需要两天最多只能完成n/2次交易。当参数给的k超过这个上限限制形同虚设硬跑 O(nk) 会超时或浪费内存。第二内层循环从k向下遍历到 1。这是滚动数组降维后的标准写法目的是让sold[j - 1]用的是上一轮上一天的值而不是本轮刚更新的值。如果从 1 向上遍历就会出现同一天内多次买入卖出的虚假收益结果偏大。这个坑我很早踩过一次AC 变成 WA 后调了半天才发现是循环方向反了。4.3 关于交易次数买入扣还是卖出扣的约定很多讨论区会把转移写成卖出时扣次数dp[i][k][0] max(dp[i-1][k][0], dp[i-1][k-1][1] prices[i]) dp[i][k][1] max(dp[i-1][k][1], dp[i-1][k][0] - prices[i])这也能跑通但返回时需要从dp[n-1][k][0]里取最大值因为可能实际完成的交易数少于 k。我自己的经验是统一用买入时扣次数面试时把这个约定提前讲清楚能避免和面试官在答案下标上产生分歧。刷题网站上两种写法都有人用不影响正确性但混着记容易串台。5. 714 手续费变体与一套能覆盖全系列的 C 模板714 在 122 的基础上加了一个变量每次买卖需要支付手续费fee。看起来只是从利润里减掉一笔钱但贪心策略会悄悄失效。5.1 为什么 714 不能直接套 122 的相邻差贪心我前面提过122 的相邻正差价累加等价于按段交易是因为没有交易成本。一旦每笔交易收费fee把一段上涨拆成多笔交易会产生多笔手续费反而更亏。比如prices [1, 3, 2, 4]fee 2一次交易是4 - 1 - 2 1而如果贪心累加所有相邻正差价第二笔交易会变成重复收费结果完全错误。所以 714 必须用状态机。只需要在买入时扣掉feeint maxProfit(vectorint prices, int fee) { int hold INT_MIN / 2; int sold 0; for (int price : prices) { int prevHold hold; int prevSold sold; sold max(prevSold, prevHold price); hold max(prevHold, prevSold - price - fee); } return sold; }至于手续费放在买入还是卖出两种写法只要全程序保持一致最终结果相同。我个人放买入因为买入时才真正花了一笔钱更贴合直觉。5.2 一套统一模板先写 188再开开关我最终沉淀下来的方法是把 188 的滚动数组写成万能模板然后根据题目要求调整状态数。int solver(int k, vectorint prices, int fee 0) { int n prices.size(); if (n 2 || k 0) return 0; if (k n / 2) { int ans 0; for (int i 1; i n; i) { if (prices[i] prices[i - 1]) ans prices[i] - prices[i - 1] - fee; } return ans; } vectorint sold(k 1, 0); vectorint hold(k 1, INT_MIN / 2); for (int price : prices) { for (int j k; j 1; --j) { sold[j] max(sold[j], hold[j] price); hold[j] max(hold[j], sold[j - 1] - price - fee); } } return sold[k]; }这个模板直接把fee融进买入操作。121 就是k1, fee0122 就是kn/2的退化分支309 需要加冷冻期状态模板不能完全覆盖但只要在sold和hold之间插入一个cool状态即可。我把这几道题的参数关系整理成了一张表方便复习时对照题目交易次数持仓状态数额外限制解法核心12112无贪心 / 双状态122无限2无贪心累加正差价12324无四变量顺序滚动188k2kk 可很大滚动数组 退化309无限3冷冻期 1 天三状态转移714无限2手续费 fee买入扣费5.3 C 实现里的一处隐藏性能点vectorint hold(k 1, INT_MIN / 2)在k很大时会导致k维数组内存飙升。所以 188 的k n / 2退化分支不仅是正确性需要也是性能需要。另一个性能点是尽量用vectorint而不是vectorvectorint因为内存连续缓存命中率高。我在刷题时会把prices改成const vectorint引用避免函数传参拷贝大数组。6. 刷完这一系列后我沉淀下的几条实测经验最后这部分不写代码了写点我在实际准备和面试过程中积累的经验。6.1 状态机 DP 的难点从来不是转移方程很多新手盯着转移方程看半天看不懂为什么是这样。我的体会是先把状态定义背下来再手写各种边界样例去验证定义是否自洽。比如 309如果一开始就把不持有拆成可买入和冷冻期转移顺理成章如果硬套 122 的两个状态怎么都补不出冷冻期逻辑。状态定义对了方程是自然而然写出来的。6.2 写 C 时先处理空数组和单元素我的代码几乎都以if (prices.empty()) return 0;开头。看起来多余但能防止后面的prices[0]越界。刷题时本地编译不会报错但某些在线评测直接返回 Runtime Error。另外n 2这个判断也建议保留因为一天内无法完成一次买卖结果必然是 0。6.3 调试时打印状态数组比脑内模拟高效得多我用 C 刷题时通常会用 VSCode 配置好调试环境遇到状态转移结果不对直接在循环里打印每天的hold和sold。有一次 188 的答案总是比预期大打印之后立刻发现内层循环方向写反了导致同一天完成了多笔交易。这类问题靠瞪眼很难发现用调试器过一遍状态数组反而很快。6.4 面试时的答题顺序建议如果面试官让你现场写买卖股票的最佳时机建议先问清楚有没有交易次数限制、有没有冷冻期、有没有手续费。这三个答案直接决定你写几个状态。我一般这样组织表达先说状态定义和复杂度O(nk) 时间和 O(k) 空间。再写核心转移方程用注释标出买入时扣次数。然后处理退化情况k 很大和边界空数组、单元素。最后用[3,2,6,5,0,3]这类用例说一遍执行过程。这个流程能让面试官觉得你是真懂而不是背了模板。最后再分享一个小技巧这一系列我建议不要按题目编号刷而是按状态复杂度从低到高刷121 - 122 - 714 - 309 - 123 - 188。这样每做一题变化只有一个变量理解成本最低。我自己在准备时把 188 的模板存成了代码片段每次遇到变体就复制出来改状态半年后再看真正留在大脑里的不是模板本身而是那套天数、剩余交易次数、是否持仓的坐标系。有了这个坐标系股票问题就不再是一堆零散题而是一道题的六个变体。