LeetCode 第123题：买卖股票的最佳时机 III

题目描述

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

难度

困难

题目链接

点击在LeetCode中查看题目

示例

示例 1：

输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
     随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

示例 2：

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。   
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3：

输入：prices = [7,6,4,3,1] 
输出：0 
解释：在这个情况下, 没有交易完成, 所以最大利润为 0。

示例 4：

输入：prices = [1]
输出：0

提示

• 1 <= prices.length <= 10^5
• 0 <= prices[i] <= 10^5

解题思路

方法一：动态规划

这道题是股票问题的扩展，限制最多进行两次交易。我们可以使用动态规划来解决。

关键点：

• 定义状态变量，表示不同交易阶段的最大利润
• 考虑每天可能的操作：买入、卖出或不操作
• 状态转移时考虑之前的最优状态

具体步骤：

1. 定义四个状态变量：
   • buy1: 第一次买入后的最大利润
   • sell1: 第一次卖出后的最大利润
   • buy2: 第二次买入后的最大利润
   • sell2: 第二次卖出后的最大利润
2. 初始化状态：
   • buy1 = -prices[0]（第一天买入）
   • sell1 = 0（还未卖出）
   • buy2 = -prices[0]（第一天买入后又卖出，然后又买入）
   • sell2 = 0（还未进行第二次卖出）
3. 遍历价格数组，对于每一天的价格：
   • 更新buy1 = max(buy1, -prices[i])（不买或今天买）
   • 更新sell1 = max(sell1, buy1 + prices[i])（不卖或今天卖）
   • 更新buy2 = max(buy2, sell1 - prices[i])（不买或今天买）
   • 更新sell2 = max(sell2, buy2 + prices[i])（不卖或今天卖）
4. 返回sell2，即最多两次交易的最大利润

时间复杂度：O(n)，其中n是数组的长度，只需要遍历一次数组 空间复杂度：O(1)，只需要常数级别的额外空间

方法二：分割数组

我们可以将问题分解为两个子问题：在某一天将价格数组分割成两部分，分别计算两部分的最大利润，然后求和。

关键点：

• 计算前i天的最大利润（第一次交易）
• 计算第i天之后的最大利润（第二次交易）
• 找到使总利润最大的分割点

具体步骤：

1. 创建两个数组leftProfit和rightProfit：
   • leftProfit[i]表示在前i天进行一次交易的最大利润
   • rightProfit[i]表示在第i天及之后进行一次交易的最大利润
2. 计算leftProfit：
   • 初始化minPrice = prices[0]
   • 遍历数组，对于每个价格，更新minPrice和leftProfit[i]
3. 计算rightProfit：
   • 初始化maxPrice = prices[n-1]
   • 从后向前遍历数组，对于每个价格，更新maxPrice和rightProfit[i]
4. 找到最大总利润：
   • 遍历所有可能的分割点i，计算leftProfit[i] + rightProfit[i+1]
   • 返回最大总利润

时间复杂度：O(n)，其中n是数组的长度，需要遍历三次数组 空间复杂度：O(n)，需要两个长度为n的数组来存储中间结果

图解思路

动态规划状态转移表

天数	价格	buy1	sell1	buy2	sell2	说明
初始状态	-	-∞	0	-∞	0	初始化状态变量
1	3	-3	0	-3	0	第一天买入，利润为-3
2	3	-3	0	-3	0	价格不变，状态不变
3	5	-3	2	-3	2	第一次卖出，利润为2；第二次买入再卖出
4	0	0	2	2	2	更新buy1为0；buy2为2
5	0	0	2	2	2	价格不变，状态不变
6	3	0	3	2	5	更新sell1为3；sell2为5
7	1	0	3	2	5	状态不变
8	4	0	4	2	6	更新sell1为4；sell2为6

分割数组方法分析表

分割点	左侧最大利润	右侧最大利润	总利润	说明
1	0	4	4	左侧只有一天，无法获利；右侧最大利润为4
2	0	4	4	左侧价格相同，无法获利；右侧最大利润为4
3	2	4	6	左侧最大利润为2；右侧最大利润为4
4	2	4	6	左侧最大利润为2；右侧最大利润为4
5	2	4	6	左侧最大利润为2；右侧最大利润为4
6	3	3	6	左侧最大利润为3；右侧最大利润为3
7	3	3	6	左侧最大利润为3；右侧最大利润为3

代码实现

C# 实现

public class Solution {
    public int MaxProfit(int[] prices) {
        if (prices == null || prices.Length <= 1) {
            return 0;
        }
        
        int buy1 = -prices[0], sell1 = 0;
        int buy2 = -prices[0], sell2 = 0;
        
        for (int i = 1; i < prices.Length; i++) {
            // 第一次买入的最大利润
            buy1 = Math.Max(buy1, -prices[i]);
            // 第一次卖出的最大利润
            sell1 = Math.Max(sell1, buy1 + prices[i]);
            // 第二次买入的最大利润
            buy2 = Math.Max(buy2, sell1 - prices[i]);
            // 第二次卖出的最大利润
            sell2 = Math.Max(sell2, buy2 + prices[i]);
        }
        
        return sell2;
    }
}

Python 实现

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices or len(prices) <= 1:
            return 0
        
        # 初始化四个状态
        buy1, sell1 = -prices[0], 0
        buy2, sell2 = -prices[0], 0
        
        for i in range(1, len(prices)):
            # 更新四个状态
            buy1 = max(buy1, -prices[i])
            sell1 = max(sell1, buy1 + prices[i])
            buy2 = max(buy2, sell1 - prices[i])
            sell2 = max(sell2, buy2 + prices[i])
        
        return sell2

C++ 实现

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() <= 1) {
            return 0;
        }
        
        int buy1 = -prices[0], sell1 = 0;
        int buy2 = -prices[0], sell2 = 0;
        
        for (int i = 1; i < prices.size(); i++) {
            // 更新四个状态
            buy1 = max(buy1, -prices[i]);
            sell1 = max(sell1, buy1 + prices[i]);
            buy2 = max(buy2, sell1 - prices[i]);
            sell2 = max(sell2, buy2 + prices[i]);
        }
        
        return sell2;
    }
};

执行结果

C# 实现

• 执行用时：168 ms
• 内存消耗：45.2 MB

Python 实现

• 执行用时：1024 ms
• 内存消耗：27.8 MB

C++ 实现

• 执行用时：112 ms
• 内存消耗：75.3 MB

性能对比

语言	执行用时	内存消耗	特点
C#	168 ms	45.2 MB	执行速度适中，内存消耗适中
Python	1024 ms	27.8 MB	执行速度较慢，内存消耗较低
C++	112 ms	75.3 MB	执行速度最快，内存消耗较高

代码亮点

1. 🎯 使用四个状态变量清晰表示不同交易阶段的最大利润
2. 💡 通过状态转移方程优化了时间复杂度，避免了暴力解法
3. 🔍 处理了边界情况，如空数组或只有一个元素的数组
4. 🎨 代码结构简洁，逻辑清晰，易于理解和维护

常见错误分析

1. 🚫 忽略了不进行任何交易的情况，导致返回负利润
2. 🚫 状态转移方程错误，没有正确考虑前一天的状态
3. 🚫 初始化状态变量不正确，影响后续计算
4. 🚫 没有考虑到可以在同一天卖出并买入，导致结果不正确

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
动态规划（四个状态变量）	O(n)	O(1)	时间和空间效率都很高	状态定义和转移较为抽象
分割数组	O(n)	O(n)	思路直观，易于理解	需要额外的空间存储中间结果
暴力解法	O(n²)	O(1)	思路最简单	时间复杂度高，会超时

相关题目

• LeetCode 121. 买卖股票的最佳时机 - 简单
• LeetCode 122. 买卖股票的最佳时机 II - 中等
• LeetCode 188. 买卖股票的最佳时机 IV - 困难
• LeetCode 309. 最佳买卖股票时机含冷冻期 - 中等
• LeetCode 714. 买卖股票的最佳时机含手续费 - 中等