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

约 6 分钟
文章信息 18 个分类 2 个标签
分类
LeetCode CodeTop 困难 未解决 50-100 面试经典 150 题 腾讯 字节 阿里 华为 微软 美团 拼多多 小米 百度 网易 快手 虾皮
标签
数组 动态规划

题目描述

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

image-20260928195727833

image-20260928195727834

题意分析

prices[i] 表示第 i 天的股价。一次交易由一次买入和随后的一次卖出组成，最多完成两笔交易，求能够获得的最大总利润。

同一时间最多持有一股，开始下一笔交易前必须卖掉上一笔持有的股票。可以买卖两次，也可以只交易一次或完全不交易；最终只计算已经卖出后得到的利润。题目限制的是交易总次数，因此不能把所有上涨区间的收益直接累加。

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

核心思路

[!blue]

枚举两次买卖的四个日期会重复计算大量相同前缀。决定今天是否买卖时，只需要知道此前处于相应交易阶段的最大现金，不需要保留具体交易日期，因此可以把过程压缩成四个状态。

这里的“现金”以初始资金 0 为基准：买入要减去股价，卖出再加回来；持股状态记录的是付过买入成本后的余额，不是当前股票的市值。处理完当前日期后：

  • buy1：第一次持股阶段的最大现金，只发生过一次买入。
  • sell1：最多完成一笔交易、当前不持股的最大现金，也允许从未交易。
  • buy2：此前最多完成一笔交易、随后再次持股的最大现金，也覆盖尚未完成过交易就买入的情况。
  • sell2：最多完成两笔交易、当前不持股的最大现金。

每个状态只有两种来源：今天不改变持仓，沿用原状态；或者今天执行这个阶段的动作，从前一阶段转移。对应更新为：

  • buy1 = max(buy1, -price)：保留旧买入，或今天第一次买入。
  • sell1 = max(sell1, buy1 + price)：保留已有利润，或卖出第一笔持股。
  • buy2 = max(buy2, sell1 - price)：在第一笔交易的利润基础上支付第二次买入成本。
  • sell2 = max(sell2, buy2 + price)：卖出后得到截至目前的累计利润。

所有合法方案在今天都属于“保持状态”或“执行当前动作”之一，所以逐日取最大值不会漏掉更优方案。第二次买入只能承接 sell1，不能承接 sell2，这就限制了交易次数，并保证两笔交易不会同时持股。

首日令 buy1 = buy2 = -prices[0]，两个卖出状态为 0。buy2 的这个初值表示可以先没有任何已完成交易就买入，两个卖出状态的零则表示允许不交易；因此状态表达的是最多两笔，不强迫做满两笔。

代码按买一、卖一、买二、卖二的顺序原地更新，后面的状态可能读取同日刚更新的值。这只会额外包含同价买卖的零收益动作：删去这些动作后，仍能得到利润相同且至多两笔的合法方案，不会虚增利润。最终返回 sell2，它已经包含两笔交易的总收益。

解题步骤

  1. 若价格数组为空，直接返回 0；否则用首日价格初始化两个买入状态，两个卖出状态初始化为 0。
  2. 从第二天开始枚举价格，先更新 buy1，再用它更新 sell1。
  3. 用 sell1 - price 更新 buy2，再用 buy2 + price 更新 sell2。
  4. 每个状态都与自身旧值取最大值，从而保留“不在今天操作”的选择。
  5. 返回 sell2，无需再与 sell1 相加。

代码实现

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
}

复杂度分析

设交易日数为 $n$。

  • 时间复杂度：$O(n)$，每个价格只触发四次常数时间的状态更新。
  • 空间复杂度：$O(1)$，只保存四个滚动状态。

关键点总结

[!green]

  • 状态保存当前交易阶段能达到的最大现金，不要求当天一定执行买卖。
  • 第二次买入接在第一次卖出之后，并承接第一笔利润。
  • 初始化允许零笔或一笔交易，最终的 sell2 已经是累计利润。

易错点总结

[!yellow]

  • 买入状态初始化为 0，相当于没有支付成本就持有股票，后续卖出会产生虚假利润。
  • 第二次买入只使用 -price，会丢失已经完成的第一笔交易利润；应从 sell1 - price 转移。
  • 让 buy2 从 sell2 - price 转移，会把两笔交易之后的利润继续用于新交易，突破次数限制。
  • 返回 sell1 + sell2 会重复计算第一笔利润，因为 sell2 已包含累计收益。
  • 把两笔交易理解为必须做满，会排除只交易一次或不交易的最优情况。

相似题目

题目 难度 关联与区别
188. 买卖股票的最佳时机 IV 困难 本题交易次数固定为2，原题扩展为k，可用按交易次数划分的持有/空仓DP。
309. 买卖股票的最佳时机含冷冻期 中等 同样对交易状态增加限制，原题限制卖出后的冷冻期，本题限制交易总次数。
121. 买卖股票的最佳时机 简单 以持有状态和交易次数描述每天的最优收益；本题最多完成两笔交易，该题只允许一次买卖。
122. 买卖股票的最佳时机 II 中等 以持有状态和交易次数描述每天的最优收益；本题最多完成两笔交易，该题允许重复买卖。
714. 买卖股票的最佳时机含手续费 中等 以持有状态和交易次数描述每天的最优收益；本题最多完成两笔交易，该题在交易转移时计入手续费。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/78561812
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！