0122. Best Time to Buy and Sell Stock II¶
题目信息¶
- 题号:
买卖股票的最佳时机 II
- 难度:
Medium
- 主题:
数组、多次交易、状态机、相邻差分贪心
- 原题:
- 重点:
先用持股/空仓状态压缩交易序列,再利用次数不限这一结构把任意上涨区间拆成全部正相邻差分
题目重述¶
给定价格数组 prices,其中 prices[i] 是第 i 天的股价。可以完成任意多笔交易,但任意时刻最多
持有一股:再次买入前必须卖出已有持仓。交易端点可以相接,不交易也是合法选择。返回最大总利润。
数组长度在 1..3 * 10^4 范围内,每个价格在 0..10^4 范围内。交易必须遵守日期顺序,不能通过
排序价格忽略时间。
自建示例¶
两段上涨:
prices = [5,2,6,1,4,7],返回10,利润为(6-2) + (7-1);连续上涨:
prices = [1,3,5,8],返回7,一次1 -> 8与逐段收集涨幅等价;持续下降:
prices = [9,6,4,1],返回0;价格不变:
prices = [4,4,4],返回0。
C++ 实现¶
#include <algorithm>
#include <vector>
class Solution {
private:
int tradingStateMachine(const std::vector<int>& prices) {
int cash = 0;
int hold = -prices[0];
for (int day = 1; day < static_cast<int>(prices.size()); ++day) {
const int previousCash = cash;
const int previousHold = hold;
cash = std::max(previousCash, previousHold + prices[day]);
hold = std::max(previousHold, previousCash - prices[day]);
}
return cash;
}
int collectPositiveDifferences(const std::vector<int>& prices) {
int profit = 0;
for (int day = 1; day < static_cast<int>(prices.size()); ++day) {
profit += std::max(0, prices[day] - prices[day - 1]);
}
return profit;
}
public:
int maxProfit(std::vector<int>& prices) {
return collectPositiveDifferences(prices);
}
};
题解¶
交易序列空间¶
允许多次交易后,候选不再是一个买卖下标对,而是若干按时间排列、互不重叠的持仓区间。直接搜索每天买入、 卖出或等待的决定会产生指数级交易序列,并且许多不同历史在某天结束时具有相同的持仓状态。
未来决策不需要知道过去每笔交易的端点,只需要知道当前是否持股,以及在该状态下已经能保留的最大现金。 这把完整交易历史压缩为两个状态。
持股与空仓状态¶
扫描完某天后定义:
cash:当天结束时不持股的最大利润;hold:当天结束时持有一股时的最大现金值,买入成本已扣除。
第一天可以不交易得到 cash = 0,或买入得到 hold = -prices[0]。之后每一天:
newCash = max(previousCash,
previousHold + price)
newHold = max(previousHold,
previousCash - price)
空仓状态来自继续空仓或今天卖出;持股状态来自继续持股或今天买入。两类来源覆盖全部合法最后动作,且都从
前一天状态转移,不会同时持有两股。最终持股仍包含未兑现股票,答案取 cash。
tradingStateMachine 保存旧状态后再更新,保持每个转移都明确来自前一天。这一 DP 已把指数交易序列降为
O(n) 时间和常量状态,适用于从规则直接推导答案。
区间利润拆分¶
本题没有交易次数上限、手续费或冷冻期,这使状态机还能进一步化简。一次从 buy 到 sell 的利润可以
写成沿途相邻差分的望远镜和:
prices[sell] - prices[buy]
= sum(prices[day] - prices[day - 1])
for day = buy + 1 .. sell
若持仓区间包含负差分,可以在下降前卖出、下降后重新买入,去掉该负项而不减少其他利润。若连续若干天都是 正差分,把每天涨幅分别实现,和在谷底买入、峰顶卖出完全相同;交易端点相接不会造成同时持有多股。
最优上界与实现¶
任意合法交易组合由若干不重叠区间组成,每笔利润都是其覆盖的相邻差分之和。删除所有非正差分只会让总和 更大,因此任何方案都不超过全数组正差分之和。
这个上界又可以实现:对每个 prices[day] > prices[day - 1] 的相邻上涨,视为前一天买入、当天卖出;
连续上涨日的相邻交易可以共享端点,下降日则保持空仓。每个正差分都被合法收集一次,所以正差分总和就是
最大利润,而不只是一个估计。
对 [5,2,6,1,4,7]:
相邻价格 |
差分 |
收集利润 |
累计利润 |
|---|---|---|---|
|
-3 |
0 |
0 |
|
4 |
4 |
4 |
|
-5 |
0 |
4 |
|
3 |
3 |
7 |
|
3 |
3 |
10 |
主解与复杂度¶
公开入口采用正差分贪心,因为它利用“次数不限且无额外交易约束”删除了显式持股状态,只保留累计利润。 状态机仍有教学价值:若以后加入手续费、冷冻期或交易次数限制,正差分结论通常失效,而状态转移可以扩展。
两种实现都扫描数组一次,时间 O(n)、额外空间 O(1)。持续下降或价格不变时没有正差分,初始利润
0 自然表示不交易。