LeetCode 123. 买卖股票的最佳时机 III

2026-07-28 HGNULB 约 5 分钟

文章信息 18 个分类 2 个标签

分类

LeetCode CodeTop 困难未解决 50-100 字节跳动微软美团阿里巴巴快手腾讯百度华为拼多多网易小米虾皮面试经典 150 题

题目描述

✅ 123. 买卖股票的最佳时机 III

题意分析

给定每天的股价，最多完成两笔交易，求最大利润。「最多」是关键：可以只做一笔，甚至一笔都不做，全程观望的利润是 0，所以答案不会是负数。

另一条硬约束是不能同时持有多笔股票：第二次买入必须发生在第一次卖出之后（同一天先卖再买是允许的）。这意味着两笔交易在时间轴上不重叠，本质是把序列切成前后两段各做一次「121 题」。

边界信号：数组可能只有一个元素（无法完成任何交易，利润 0）；价格可能一路下跌（不交易即最优）。n 可达 $10^5$，枚举分割点再对每段线性扫一遍的 $O(n^2)$ 做法会超时。

解法：四状态股票动态规划

核心思路

问题关键：最多完成两笔交易，且再次买入前必须先卖出。枚举两笔交易的四个日期是 $O(n^4)$；枚举分割点并反复求左右最大利润也会产生重复计算。

为什么选四状态动态规划：每天只需记录四种最优现金：buy1（第一次买入后持股）、sell1（第一次卖出后空仓）、buy2（第二次买入后持股）、sell2（第二次卖出后空仓）。每个状态都只依赖前一个交易阶段，可以滚动成四个变量。

状态定义与正确性：四个变量表示处理完当前价格前缀后，处于对应阶段时能拥有的最大现金。转移分别为 max(保持原状态, 今天执行该动作)：buy1 = max(buy1, -price)，sell1 = max(sell1, buy1 + price)，buy2 = max(buy2, sell1 - price)，sell2 = max(sell2, buy2 + price)。buy2 只能从 sell1 转移，所以两笔交易不会重叠；每个合法交易序列都能沿这四个阶段到达，取最大值不会漏解。

同一天按上述顺序更新是安全的：当天买入再卖出只会增加一笔利润为 0 的空交易，不可能虚增答案，反而自然覆盖“少于两笔交易”的情况。

解题步骤

若数组为空返回 0；否则用第一天价格初始化 buy1 = buy2 = -prices[0]，两个卖出状态为 0。

从第二天开始遍历，按 buy1 → sell1 → buy2 → sell2 更新四个状态。

第一次买入只依赖初始现金 0；第一次卖出依赖 buy1；第二次买入必须依赖 sell1；最终卖出依赖 buy2。

遍历结束返回 sell2。它已经是两次卖出阶段的累计利润，不需要再与 sell1 相加。

对 [3,3,5,0,0,3,1,4]，可以先在 3 买、5 卖赚 2，再在 0 买、4 卖赚 4，四状态最终得到最大利润 6。

代码实现

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length == 0) {
            return 0;
        }

        int buy1 = -prices[0];
        int sell1 = 0;
        int buy2 = -prices[0];
        int sell2 = 0;

        for (int i = 1; i < prices.length; i++) {
            int price = prices[i];
            buy1 = Math.max(buy1, -price);
            sell1 = Math.max(sell1, buy1 + price);
            buy2 = Math.max(buy2, sell1 - price);
            sell2 = Math.max(sell2, buy2 + price);
        }

        return sell2;
    }
}

func maxProfit(prices []int) int {
    if len(prices) == 0 {
        return 0
    }

    buy1 := -prices[0]
    sell1 := 0
    buy2 := -prices[0]
    sell2 := 0

    for _, price := range prices[1:] {
        buy1 = maxInt(buy1, -price)
        sell1 = maxInt(sell1, buy1+price)
        buy2 = maxInt(buy2, sell1-price)
        sell2 = maxInt(sell2, buy2+price)
    }

    return sell2
}

func maxInt(a int, b int) int {
    if a > b {
        return a
    }
    return b
}

复杂度分析

时间复杂度：$O(n)$，每个价格只进行四次状态更新。

空间复杂度：$O(1)$，只保留四个滚动状态。

关键点总结

状态表示“处理完当前前缀后的最大现金”，不是“今天必须执行某动作”。

buy2 从 sell1 转移，是两笔交易按顺序且不重叠的关键。

sell2 已包含前两笔交易的总利润，直接返回即可。

推广到最多 k 笔交易时，将四个变量扩展为 buy[1..k]、sell[1..k]。

易错点总结

买入状态初始化为 0：[5,3] 会变成未买先卖并产生虚假利润，必须初始化为 -prices[0]。

第二次买入从 -price 转移：会丢掉第一笔利润；应使用 sell1 - price。

返回 sell1 + sell2：sell2 已经是累计利润，相加会重复计算；[1,2] 会错误得到 2。

把“最多两笔”写成“必须两笔”：[1,2] 只做一笔最优，答案仍应为 1。

让 buy2 从 sell2 - price 转移：这会把已完成两笔后的利润再次用于买入，等价于放开交易次数；[1,2,1,2,1,2] 会错误得到 3，而最多两笔只能得到 2。

相似题目

题目	难度	考察点
121. 买卖股票的最佳时机	简单	单笔交易，维护历史最低价即可
122. 买卖股票的最佳时机 II	中等	交易次数不限，可贪心累加正涨幅
188. 买卖股票的最佳时机 IV	困难	本题推广到 k 笔，状态变量升级为数组
309. 买卖股票的最佳时机含冷冻期	中等	卖出后隔一天才能买，状态机加冷冻边
714. 买卖股票的最佳时机含手续费	中等	每笔交易扣固定费用，转移式减去手续费
剑指 Offer 63. 股票的最大利润	中等	121 的镜像题，练习单笔交易模板