type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给定一个数组,它的第
i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算能获取的最大利润。
最多可以完成两笔交易, 且不能同时参与多笔交易(即必须在再次购买前出售掉之前的股票)。
示例 1:
示例 2:
示例 3:
示例 4:
解法一:暴力枚举
我们先从最直观的角度想: 既然只能买卖两次,那不就是把价格数组切成两段嘛?
第一段做第一次买卖,第二段做第二次买卖。
举个例子,比如
[3,3,5,0,0,3,1,4],我们可以在不同的天数中间分一刀,比如:- 第 0~3 天是第一笔交易;
- 第 4~7 天是第二笔交易。
那么我们就可以:
- 枚举所有可能的分割点;
- 对每一段都算一次“买卖股票的最佳时机(只能买卖一次)”;
- 两段的利润加起来,取最大值。
复杂度
- 时间:O(n²),因为每次分割都要重新遍历一遍。会超时。
- 空间:O(1)。
解法二:动态规划 (推荐)
因为题目限制最多只能做两次交易,所以我们最多会经历四个操作阶段:
- 第一次买入(buy1)
- 可能在前一天已经买过;
- 或者今天刚买。
所以取两种情况中的最大值: buy1 = max(buy1, -price)
(因为买入要花钱,所以利润是负的。)
- 第一次卖出(sell1)
- 可能昨天就已经卖掉;
- 或者今天卖。
今天卖的话,你之前必须处于买入状态:
sell1 = max(sell1, buy1 + price)
- 第二次买入(buy2)
- 可能昨天已经买了;
- 或者今天买;
今天买就得用第一次卖出的利润再去买:
buy2 = max(buy2, sell1 - price)
- 第二次卖出(sell2)
- 可能昨天已经卖完;
- 或者今天卖;
今天卖时,你手上之前得有第二次的买入状态:
sell2 = max(sell2, buy2 + price)
整个交易顺序必须是: 买 → 卖 → 买 → 卖
我们用四个变量来记录截至当前天数时,在这四种状态下我们能得到的最大利润。
在开始之前,我们可以初始化为:
buy1 = -∞:因为还没买;
sell1 = 0:还没卖,利润是 0;
buy2 = -∞:还没第二次买;
sell2 = 0:还没第二次卖。
复杂度
- 时间:O(n),我们只遍历一遍价格数组;
- 空间:O(1),只用了 4 个变量。
解法三:动态规划数组版
用标准 DP 数组形式,写成二维 DP 表。
假设
dp[i][k][0/1] 表示:- 到第
i天;
- 最多允许做
k次交易;
0/1表示手中是否持有股票(0:没持有,1:持有);
- 状态值表示最大利润。
状态转移方程
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + price[i])# 今天没股票
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - price[i])# 今天有股票
复杂度
- 时间:O(n × K),这里只有两次交易,所以其实还是 O(n);
- 空间:O(n × K × 2),可以用滚动数组优化到 O(K)。
- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode-123-买卖股票的最佳时机-iii
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。
上一篇
[Leetcode 122] 买卖股票的最好时间 II
下一篇
[Leetcode 124] 二叉树中的最大路径和