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

Categories:

Tags:

题目描述
思路分析
1. 解法一：状态机动态规划（推荐）
相似题目

题目描述

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

思路分析

解法一：状态机动态规划（推荐）

核心思路：

只允许两次交易，可用四个状态表示：

buy1、sell1、buy2、sell2 分别表示第一次买入/卖出、第二次买入/卖出的最大收益。

遍历价格，依次更新四个状态即可。

复杂度分析：

时间复杂度：O(n)，其中 n 表示价格数组长度。

空间复杂度：O(1)，仅使用常数额外空间。

class Solution {
    public int maxProfit(int[] prices) {
        int buy1 = Integer.MIN_VALUE;
        int sell1 = 0;
        int buy2 = Integer.MIN_VALUE;
        int sell2 = 0;

        for (int price : prices) {
            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 {
	buy1 := -1 << 60
	sell1 := 0
	buy2 := -1 << 60
	sell2 := 0

	for _, price := range prices {
		if -price > buy1 {
			buy1 = -price
		}
		if buy1+price > sell1 {
			sell1 = buy1 + price
		}
		if sell1-price > buy2 {
			buy2 = sell1 - price
		}
		if buy2+price > sell2 {
			sell2 = buy2 + price
		}
	}

	return sell2
}

相似题目

题目	难度	考察点
121. 买卖股票的最佳时机	简单	动态规划
122. 买卖股票的最佳时机 II	中等	动态规划
188. 买卖股票的最佳时机 IV	困难	动态规划
309. 最佳买卖股票时机含冷冻期	中等	动态规划
714. 买卖股票的最佳时机含手续费	中等	动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/78561812