力扣123买卖股票的最佳时机III是我刷股票系列时卡得最久的一道题。它允许你在一个价格数组上完成最多两笔交易求最大利润第121题只需要一次交易第122题不限交易次数到了这里次数被卡成两笔表面上只是多了一个限制解题思路却完全不同。我最初想当然地把数组切两段各找一次最大利润结果验证之后才发现两笔交易并不是两个独立区间的简单相加中间被回调吃掉的那部分利润才是真正的分水岭。这篇文章会把从错误直觉到正确状态机的完整推导过程、Java实现、初始化陷阱以及这道题如何串起整个股票买卖系列一次讲清楚。1. 两次交易为什么不能直接拆两段找最大值先灭掉最常见的错误直觉1.1 朴素拆分法的思路与代价遇到最多两次交易绝大多数人的第一反应都是枚举切分点把数组从某个位置k切成两段左边[0, k]完成第一笔交易右边[k1, n-1]完成第二笔交易最后把两段最大利润加起来遍历所有k取最大值。这个思路本身没有错它确实能算出正确答案。实现上可以分两步预处理left[i]从第0天到第i天只做一次交易能拿到的最大利润。计算方式是维护到当前为止的最低价格每天尝试今天卖出。right[i]从第i天到最后一天只做一次交易能拿到的最大利润。计算方式是从右往左维护当前遇到的最高价格每天尝试今天买入。最后答案就是遍历切分点k求 max(left[k] right[k 1])。这个解法的时间复杂度是O(n)空间复杂度是O(n)需要额外两个数组。问题在哪里一是代码量明显变长边界下标很容易写错尤其是right数组的下标i到底表示这段区间从哪一天开始这种细节在面试现场紧张的时候特别容易翻车。二是推广性差如果把题目改成最多K笔交易力扣188这种两段式的写法完全无法直接扩展你得另起炉灶。三是这个解法本身没有揭示交易次数这个限制条件的本质做完一道题对系列其他题目几乎没有帮助。真正想在面试中拿下这类题目需要的是一种能从1笔推广到K笔的通用框架。这就是状态机DP。1.2 一个反例看穿先找最大区间的陷阱在引入状态机之前值得先看一个反例理解为什么贪心地先找最大利润区间会失败。考虑价格数组 [1, 3, 2, 6]。一次交易的最大利润是多少第0天价格1买入第3天价格6卖出利润5。这是全局最优区间没毛病。但看看两笔交易呢第0天价格1买入第1天价格3卖出利润2第2天价格2买入第3天价格6卖出利润4。两笔加起来是6反而比最大一次交易的5还要高。这就是这个反例的价值它证明了先锁定全局最大的一次交易区间再在左右两边继续找这种贪心策略是错的。为什么错因为全局最大的一次交易区间 [1, 6] 把中间从3跌到2的那段回调给吞掉了。这个回调本身是个独立低点完全可以作为第二笔交易的入场点如果你硬要把它包进同一笔交易就等于在2块钱的低点没有补仓把额外的4块钱利润白白扔了。所以题目允许你做两次交易时最优解不一定包含最大的一次交易。你需要一种机制让两笔交易的决策可以互相影响、动态交叉。状态机DP就是干这件事的。2. 状态机DP的建模过程把交易过程变成一条状态链路2.1 四个状态变量到底代表了什么状态机DP的核心想法是不要试图同时考虑选哪两个区间而是把一个人的持仓和交易进度拆成几个阶段每个阶段用一个状态变量记录在当前阶段的约束下手上的最大现金量。对于最多两次交易完整的过程是空仓 → 第一次买入 → 第一次卖出 → 第二次买入 → 第二次卖出。其中买入和卖出各两次对应四个需要记录的状态。我习惯把这四个变量命名为 firstBuy、firstSell、secondBuy、secondSell含义如下表状态变量含义持有股票已完成的交易次数firstBuy第一次买入后的最大现金通常为负数表示花掉的钱持有1支0次完成的交易firstSell第一次卖出后的最大现金空仓已完成1次交易secondBuy第二次买入后的最大现金持有1支已完成1次交易secondSell第二次卖出后的最大现金最终答案空仓已完成2次交易很多题解把这四个变量叫 buy1、sell1、buy2、sell2本质是同一个东西。我推荐用完整语义命名因为在面试讲题时firstBuy这个名字能直接让人听出它代表第一阶段买入而不是一个无意义的编号。需要注意这里说的最大现金是一个账面概念不是真实账户余额。初始状态空仓时现金为0买入后现金变成负数因为你付出去钱、换回股票卖出后现金变成正数股票换回钱。在遍历价格的过程中这四个状态变量会互相传递信息最终 secondSell 就是在所有约束条件下能拿到的最大现金也就是最大利润。2.2 转移方程怎么推逐行翻译成人话每天来一个新价格 prices[i]我们要用这个价格去尝试刷新四个状态。这里最忌讳死记公式我建议你跟我一起把每一行翻译成正常的商业逻辑。第一笔买入firstBuy Math.max(firstBuy, -prices[i]);这行的意思是如果不买保持原来的 firstBuy如果今天买入那我的现金就是 -prices[i]花出去这么多钱。取 max就是让买入后剩余现金最多也就是以最便宜的价格买入。所以 firstBuy 最后会收敛到最优的第一笔买入成本的相反数。第一笔卖出firstSell Math.max(firstSell, firstBuy prices[i]);这行的意思是如果今天不卖保持原来的 firstSell如果今天卖出那么第一次买入后剩余的现金加上今天卖股票拿到的钱就是完成第一笔交易后的总现金。注意这里的 firstBuy 必须是本轮更新之后的值也就是说当天先买入再卖出这个虚拟操作是被允许的利润为0不影响全局最优解。第二笔买入secondBuy Math.max(secondBuy, firstSell - prices[i]);这行是整个状态机里最难理解的一行。翻译成人话我已经靠第一笔交易攒下了 firstSell 这么多现金此时空仓如果今天我决定启动第二笔交易、买入股票那么买入完成后手里的现金就是 firstSell - prices[i]。取 max 表示用这笔钱尽量买在更低的价格让买入后剩余现金最多。第二笔卖出secondSell Math.max(secondSell, secondBuy prices[i]);这行就好理解了手里有了第二次买入后的股票账面现金是 secondBuy今天卖出最终现金是 secondBuy prices[i]取 max 就是最终的最大盈利。整个状态转移链路是单向的firstBuy → firstSell → secondBuy → secondSell。每一步都只依赖前一个状态不会出现未来价格倒推过去的情况所以一趟线性遍历就能完成所有计算。3. 边界初始化与Java实现这题最容易翻车的地方3.1 初始化为什么是-prices[0]而不是0或Integer.MIN_VALUE很多人在状态转移方程能理解的情况下依然在初始化上栽跟头。最常见的困惑是firstBuy 初始化为0行不行secondBuy 初始化为 Integer.MIN_VALUE 行不行先说 firstBuy。第0天如果什么都不做现金是0但如果第0天买入现金是 -prices[0]。我们要求的是买入后的最大现金所以 firstBuy 应该初始化为 -prices[0]表示我在第0天就完成了第一次买入。如果初始化为0等号右边的 Math.max(0, -prices[i]) 在价格为正时永远是0等于告诉DP我永远不会买入这显然错误。再说 secondBuy。最稳妥的写法是同样初始化为 -prices[0]。语义上可以这样解释第0天我可以同时完成买入第一笔、卖出第一笔、再买入第二笔这三个动作其中买入-卖出的利润为0所以 secondBuy 在起点就是 -prices[0]。有些实现会把 firstBuy 和 secondBuy 初始化为 Integer.MIN_VALUE然后在循环中从 i0 开始更新。这种做法在 C 里也能跑通但在 Java 里有一个隐患如果某一天出现了 Integer.MIN_VALUE prices[i]会导致整数溢出。虽然 Math.max(0, 负数) 最终还是会保住0但这个溢出是隐性的排查起来非常痛苦。我的建议是统一用 -prices[0] 初始化简单、直观、不溢出。面试官如果追问为什么你就说这是允许同一天虚拟交易的语义不影响最优解。3.2 完整Java实现与变量更新顺序下面是完整的 Java 实现。注意循环从 i1 开始因为第0天的状态已经在初始化里定义好了。public int maxProfit(int[] prices) { if (prices null || prices.length 2) { return 0; } // 第0天完成第一次买入账上现金为负的股价 int firstBuy -prices[0]; // 第一次卖出后什么都没做现金为0 int firstSell 0; // 第0天也可以完成一次虚拟的买入-卖出-再买入 int secondBuy -prices[0]; // 两笔交易全部结束时现金为0 int secondSell 0; for (int i 1; i prices.length; i) { firstBuy Math.max(firstBuy, -prices[i]); firstSell Math.max(firstSell, firstBuy prices[i]); secondBuy Math.max(secondBuy, firstSell - prices[i]); secondSell Math.max(secondSell, secondBuy prices[i]); } return secondSell; }时间复杂度 O(n)空间复杂度 O(1)这已经是这题的最优解形态。关于变量更新顺序有一个必须养成的习惯在同一轮循环里严格按照 firstBuy → firstSell → secondBuy → secondSell 的顺序更新。如果调换顺序比如先把 firstSell 算出来再用旧 firstBuy语义上就变成了不允许当天买入后卖出虽然因为同一天买卖利润为0最终答案往往不会变但在状态机的完整性上是缺陷。提示如果你想在代码里顺手做防御最后写成 return Math.max(firstSell, secondSell) 也没有问题因为 firstSell 代表只做一笔交易的情况secondSell 代表做两笔交易的情况取 max 是最严谨的。只不过数学上 secondSell 恒不小于 firstSell所以直接返回 secondSell 即可。4. 跑测试用例与复盘常见错误从提交记录里总结教训4.1 官方示例与经典用例验证口说无凭我跑了一批用例来验证这段实现。理解这些用例为什么能得到对应输出比记住答案更重要。输入数组期望输出最优交易路径[3,3,5,0,0,3,1,4]6第3天0买、第5天3卖利润3第6天1买、第7天4卖利润3总计6[1,2,3,4,5]4第0天1买、第4天5卖利润4一次交易即可拆成两笔也是4[7,6,4,3,1]0一直下跌不交易[1,3,2,6]6第0天1买、第1天3卖利润2第2天2买、第3天6卖利润4总计6[1,2,4,2,5,7,2,4,9,0]13第0天1买、第5天7卖利润6第6天2买、第8天9卖利润7总计13最后一个用例很值得手工推一遍。它说明了一个重要现象第一笔交易并不一定是全局最大利润区间它只是在给第二笔交易留出足够空间的前提下第一笔本身的最优。你甚至可以观察到在第8天之前secondSell 的值从8升到13靠的是 secondBuy 在第6天附近锁定了低点2然后等到9才卖出。4.2 我从错误提交里总结的三个翻车点我在最开始写这题的时候提交错了好几次总结下来核心就三个坑。第一个坑是 secondBuy 每次都用「上一轮的 firstSell」去减今天的价格。如果我不小心把更新顺序写成 firstSell 在 firstBuy 之前那么当天买入的第一笔无法参与当天卖出的计算。这个问题在单调递增的数组上通常看不出来但一旦价格剧烈波动就有可能在极端用例上差一个0利润的转折点导致答案偏小。第二个坑是初始化把 secondBuy 写成 0。表面上看0代表空仓现金似乎很合理但实际上它会污染后面的 secondSell因为 secondBuy 为0时secondBuy prices[i] 会把当天买入当天卖出利润为0错误地变成用0元买入股票再卖出赚价格差价这在语义上等于凭空多了一笔免费买入的机会答案会虚高。用 -prices[0] 初始化就没有这个问题。第三个坑是忘记处理 prices.length 2 的边界。如果数组长度是0或1代码直接访问 prices[0] 会抛数组越界异常或者单独返回0。我在自己测试时 Mock 了一个空数组第一版实现直接崩了。这个防御判断必须加在最前面。另外建议你在本地调试时把每一轮循环后的四个值打印出来。比如用 [1,2,4,2,5,7,2,4,9,0] 这个用例第8天价格9时 secondSell 会突然跳到13。你会直观地看到 secondBuy 如何在低价区被压低、然后在反弹日释放出利润这种盯着状态量变化的调试方式比对着答案猜原因高效得多。5. 这道题真正的价值一张状态机串起整个股票买卖系列5.1 从一维到四维股票系列的难度阶梯力扣股票系列一共有六道题核心都是同一个状态机思想只是状态数量和转移条件不同。把这六道题放在一起看会非常清晰题目交易次数额外限制状态数量1211次无2个买入/卖出122无限次无2个但当天可连续买卖1232次无4个两次买卖各成状态188K次无2K个309无限次卖出后有一天冷冻期3个持有/冷冻/可买714无限次每次交易有手续费2个卖出时扣手续费也就是说第123题不是孤立的一道题它是第121题的四状态推广又是第188题的特例当K2。理解了123121就是砍掉一半状态的简化版188就是K次循环套同一个转移公式309和714则是在这个框架上增加状态或费用项。5.2 把两笔推广到K笔力扣188的通用模板如果只满足于背下四行转移方程这道题的价值就被浪费了。我建议你至少看一眼K次的通用写法因为这道题的扩展问在面试里很常见把数组从两笔推广到K笔用两个长度为K的数组滚动更新。public int maxProfit(int k, int[] prices) { if (prices null || prices.length 2 || k 0) { return 0; } // 如果K比最多有效交易次数还大等价于无限次交易 if (k prices.length / 2) { int profit 0; for (int i 1; i prices.length; i) { if (prices[i] prices[i - 1]) { profit prices[i] - prices[i - 1]; } } return profit; } int[] buy new int[k]; int[] sell new int[k]; for (int i 0; i k; i) { buy[i] -prices[0]; } for (int i 1; i prices.length; i) { buy[0] Math.max(buy[0], -prices[i]); sell[0] Math.max(sell[0], buy[0] prices[i]); for (int j 1; j k; j) { buy[j] Math.max(buy[j], sell[j - 1] - prices[i]); sell[j] Math.max(sell[j], buy[j] prices[i]); } } return sell[k - 1]; }这个通用模板其实就是123的循环展开版本。当k2时buy[0]、sell[0]、buy[1]、sell[1]就是之前的firstBuy、firstSell、secondBuy、secondSell。写到这里你会发现123的核心价值不在那四行代码而在交易次数如何转化为有限状态的建模思想。面试官还有一个高频追问为什么允许同一天先卖后买不会破坏答案原因是同一天卖和买利润为0相当于一次无意义的空转如果最优解需要在这一天完成一次切换空转能帮你进入下一笔交易的状态如果不需要空转也不会增加任何利润。所以状态机里引入这种虚拟交易是安全的它只是在枚举所有可行策略时多提供了一个无关紧要的选项。我在实际刷题中的体会是这道题值得花一整晚去拆透。先用拆分法写出一个能过的版本再用状态机重写一次接着把K次推广写一遍最后拿 [1,3,2,6] 和 [1,2,4,2,5,7,2,4,9,0] 手推每一个状态量。走完这一遍121、122、123、188在脑子里会自然贯通成一张表而不是四段孤立代码。那份通透感才是这道题留给你最值钱的东西。