题解 | 买卖股票的最好时机(三)

1、解题思路

1. 动态规划：定义四个状态变量： buy1：第一次买入股票后的最大利润。sell1：第一次卖出股票后的最大利润。buy2：第二次买入股票后的最大利润。sell2：第二次卖出股票后的最大利润。初始化： buy1 = -prices[0]，表示第一次买入后的利润为负的买入价格。sell1 = 0，表示第一次卖出后的利润为 0（还未卖出）。buy2 = -prices[0]，表示第二次买入后的利润为负的买入价格。sell2 = 0，表示第二次卖出后的利润为 0（还未卖出）。状态转移： buy1 = max(buy1, -prices[i])：第一次买入后的利润为当前买入的负价格或之前的买入利润。sell1 = max(sell1, buy1 + prices[i])：第一次卖出后的利润为当前卖出的利润或之前的卖出利润。buy2 = max(buy2, sell1 - prices[i])：第二次买入后的利润为第一次卖出后的利润减去当前买入价格或之前的买入利润。sell2 = max(sell2, buy2 + prices[i])：第二次卖出后的利润为第二次买入后的利润加上当前卖出价格或之前的卖出利润。最终结果为 sell2，即第二次卖出后的最大利润。
2. 关键点：最多进行两次买卖操作，不能同时持有两笔股票。通过四个状态变量跟踪两次买卖的利润变化。一次遍历即可完成，时间复杂度 O(n)，空间复杂度 O(1)。

2、代码实现

C++

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 两次交易所能获得的最大收益
     * @param prices int整型vector 股票每一天的价格
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        // write code here
        if (prices.empty()) {
            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;
    }
};

Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 两次交易所能获得的最大收益
     * @param prices int整型一维数组 股票每一天的价格
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        // write code here
        if (prices.length == 0) 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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 两次交易所能获得的最大收益
# @param prices int整型一维数组 股票每一天的价格
# @return int整型
#
class Solution:
    def maxProfit(self , prices: List[int]) -> int:
        # write code here
        if not prices:
            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

3、复杂度分析

• 时间复杂度 O(n)
• 空间复杂度 O(1)