0123. Best Time to Buy and Sell Stock III
=========================================
题目信息
--------
:题号: 0123. 买卖股票的最佳时机 III
:难度: Hard
:主题: 数组、有限交易次数、前后缀最优、交易状态机
:原题: `LeetCode 0123 `_
:重点: 从四个交易端点的搜索,先用分割日组合两次单笔最优,再压缩为买一、卖一、买二、卖二四阶段
题目重述
--------
给定价格数组 ``prices``,最多完成两笔交易。每笔交易由一次买入和之后的一次卖出组成;任意时刻最多持有
一股,因此第二次买入只能在第一次卖出后进行。可以只做一笔或完全不交易,返回最大总利润。
数组长度在 ``1..10^5`` 范围内,每个价格在 ``0..10^5`` 范围内。交易必须遵守日期顺序,不能让两段持仓
区间重叠。
自建示例
--------
* 两段交易:``prices = [6,1,5,2,8,3,9]``,返回 ``13``,可做 ``1 -> 8`` 与 ``3 -> 9``;
* 只有一段上涨:``prices = [1,2,3,4]``,返回 ``3``,不必强制完成两笔;
* 持续下降:``prices = [5,4,3]``,返回 ``0``;
* 单天:``prices = [7]``,返回 ``0``。
C++ 实现
--------
.. code-block:: cpp
#include
#include
class Solution {
private:
int splitPrefixAndSuffix(const std::vector& prices) {
const int count = static_cast(prices.size());
std::vector prefixProfit(count);
std::vector suffixProfit(count);
int lowestPrice = prices[0];
for (int day = 1; day < count; ++day) {
lowestPrice = std::min(lowestPrice, prices[day]);
prefixProfit[day] = std::max(prefixProfit[day - 1], prices[day] - lowestPrice);
}
int highestPrice = prices[count - 1];
for (int day = count - 2; day >= 0; --day) {
highestPrice = std::max(highestPrice, prices[day]);
suffixProfit[day] = std::max(suffixProfit[day + 1], highestPrice - prices[day]);
}
int maximumProfit = 0;
for (int split = 0; split < count; ++split) {
maximumProfit = std::max(maximumProfit, prefixProfit[split] + suffixProfit[split]);
}
return maximumProfit;
}
int fourTradingStages(const std::vector& prices) {
int firstBuy = -prices[0];
int firstSell = 0;
int secondBuy = -prices[0];
int secondSell = 0;
for (int day = 1; day < static_cast(prices.size()); ++day) {
const int previousFirstBuy = firstBuy;
const int previousFirstSell = firstSell;
const int previousSecondBuy = secondBuy;
const int previousSecondSell = secondSell;
firstBuy = std::max(previousFirstBuy, -prices[day]);
firstSell = std::max(previousFirstSell, previousFirstBuy + prices[day]);
secondBuy = std::max(previousSecondBuy, previousFirstSell - prices[day]);
secondSell = std::max(previousSecondSell, previousSecondBuy + prices[day]);
}
return secondSell;
}
public:
int maxProfit(std::vector& prices) {
return fourTradingStages(prices);
}
};
题解
----
四个端点
~~~~~~~~
两笔交易可以由 ``buy1 < sell1 <= buy2 < sell2`` 四个时间端点描述。直接枚举所有有序四元组能覆盖全部候选,
但最坏需要四层搜索;还要把只做一笔和不交易作为额外情况。
交易不重叠提供了一个划分结构:总能找到某一天,把第一笔完整放在该日前缀,把第二笔完整放在该日后缀。
与其同时选择四个端点,可以先固定前后两段的分界。
分割日前后缀
~~~~~~~~~~~~
``prefixProfit[i]`` 表示日期 ``[0,i]`` 内最多一笔交易的最大利润,可在从左到右扫描中维护历史最低买价;
``suffixProfit[i]`` 表示日期 ``[i,n)`` 内最多一笔交易的最大利润,可从右向左维护未来最高卖价。
对每个 ``split``,``prefixProfit[split] + suffixProfit[split]`` 组合两段互不交叉的单笔最优。任意合法两笔交易
都能选择位于第一次卖出与第二次买入之间的分割日,因此会被某次组合覆盖;两张表中的 ``0`` 又允许某一段
不交易。
``splitPrefixAndSuffix`` 把四端点搜索降为三次线性扫描,但两张长度 ``n`` 的数组只为最后的组合服务。还可以
不显式枚举分割日,而是在每天结束时记录交易已经推进到哪个阶段。
四阶段状态
~~~~~~~~~~
扫描到某天后,合法历史按操作进度压缩为:
.. code-block:: text
firstBuy 完成第一次买入后,持股状态的最大现金
firstSell 完成第一次卖出后,空仓状态的最大利润
secondBuy 完成第二次买入后,持股状态的最大现金
secondSell 完成第二次卖出后,空仓状态的最大利润
每个状态都允许“至多推进到该阶段”,因此初始两个卖出状态为 ``0``,两个买入状态为 ``-prices[0]``;这让
不交易或只做一笔自然包含在后续最优值中,不必强制执行两次盈利交易。
每天以价格 ``price`` 更新:
.. code-block:: text
firstBuy' = max(firstBuy, -price)
firstSell' = max(firstSell, firstBuy + price)
secondBuy' = max(secondBuy, firstSell - price)
secondSell' = max(secondSell, secondBuy + price)
每个第一项表示当天不执行该阶段操作,第二项表示由紧邻的前一阶段在今天完成买入或卖出。``secondBuy`` 可能
为正数,因为第一次交易的利润可以在支付第二次买入后仍留下正现金。
更新顺序
~~~~~~~~
代码先保存四个前一天快照,再统一计算新状态。这样第二次买入明确来自此前已经完成第一次卖出的历史,第二次
卖出也来自此前持有第二股的历史;状态边界不依赖同一天更新后的值。即使题目允许交易端点相接,快照写法仍让
转移来源最容易验证。
对 ``[6,1,5,2,8,3,9]``:
.. list-table::
:header-rows: 1
* - 处理价格
- ``firstBuy``
- ``firstSell``
- ``secondBuy``
- ``secondSell``
* - 6
- -6
- 0
- -6
- 0
* - 1
- -1
- 0
- -1
- 0
* - 5
- -1
- 4
- -1
- 4
* - 2
- -1
- 4
- 2
- 4
* - 8
- -1
- 7
- 2
- 10
* - 3
- -1
- 7
- 4
- 10
* - 9
- -1
- 8
- 4
- 13
最终必须空仓,``secondSell = 13`` 同时覆盖至多零、一、两笔交易的最优方案。
主解与复杂度
~~~~~~~~~~~~
公开入口采用四阶段状态机,因为它把前后缀数组和分割日扫描压缩为四个整数,同时直接维护交易顺序。与无限
次交易不同,不能简单收集所有正差分;上涨段超过两段时必须选择或合并最有价值的两次交易。
前后缀方法时间 ``O(n)``、空间 ``O(n)``;四状态主解时间 ``O(n)``、额外空间 ``O(1)``。价格与最多两笔
利润之和都在 32 位整数范围内。