0121. Best Time to Buy and Sell Stock¶
题目信息¶
- 题号:
买卖股票的最佳时机
- 难度:
Easy
- 主题:
数组、下标对枚举、前缀最小值、单次扫描
- 原题:
- 重点:
固定交易一端后删除另一端的重复搜索,再把后缀数组压缩为扫描中的历史最低价
题目重述¶
给定整数数组 prices,其中 prices[i] 是第 i 天的股票价格。最多完成一笔交易:选择一天买入,
再选择严格更晚的一天卖出,利润为卖出价减买入价。也可以不交易,因此最大利润不会小于 0。
数组长度在 1..10^5 范围内,每个价格在 0..10^4 范围内。不能排序后再配对,因为数组下标表示时间。
自建示例¶
中途低点买入:
prices = [9,4,7,2,8,5],返回6,在价格2时买入、价格8时卖出;最低价位于最后:
prices = [5,8,2],返回3,不能把最后的2与此前的8反向配对;无利润:
prices = [3,3,2,2],返回0;单天:
prices = [7],没有合法买卖日对,返回0。
C++ 实现¶
#include <algorithm>
#include <vector>
class Solution {
private:
int enumerateTransactions(const std::vector<int>& prices) {
int maximumProfit = 0;
for (int buy = 0; buy < static_cast<int>(prices.size()); ++buy) {
for (int sell = buy + 1; sell < static_cast<int>(prices.size()); ++sell) {
maximumProfit = std::max(maximumProfit, prices[sell] - prices[buy]);
}
}
return maximumProfit;
}
int suffixMaximumPrices(const std::vector<int>& prices) {
const int count = static_cast<int>(prices.size());
std::vector<int> highestFrom(count);
highestFrom[count - 1] = prices[count - 1];
for (int day = count - 2; day >= 0; --day) {
highestFrom[day] = std::max(prices[day], highestFrom[day + 1]);
}
int maximumProfit = 0;
for (int buy = 0; buy + 1 < count; ++buy) {
maximumProfit = std::max(maximumProfit, highestFrom[buy + 1] - prices[buy]);
}
return maximumProfit;
}
int prefixMinimumPrice(const std::vector<int>& prices) {
int lowestEarlierPrice = prices[0];
int maximumProfit = 0;
for (int sell = 1; sell < static_cast<int>(prices.size()); ++sell) {
maximumProfit = std::max(maximumProfit, prices[sell] - lowestEarlierPrice);
lowestEarlierPrice = std::min(lowestEarlierPrice, prices[sell]);
}
return maximumProfit;
}
public:
int maxProfit(std::vector<int>& prices) {
return prefixMinimumPrice(prices);
}
};
题解¶
交易下标对¶
原始搜索空间是所有满足 buy < sell 的下标对。enumerateTransactions 固定买入日后枚举所有更晚卖出日,
恰好检查每笔合法交易一次;maximumProfit 从 0 开始,使全部价差非正时选择不交易。
长度为 n 时共有 n(n - 1) / 2 个候选,时间为 O(n²)。每次价差计算很便宜,瓶颈是对不同买入日
反复寻找其右侧的最高价格,或对不同卖出日反复寻找其左侧的最低价格。
固定买入日¶
若买入日 buy 已定,最佳卖出价就是严格位于其后的最高价格。suffixMaximumPrices 从右向左预处理:
highestFrom[day] = max(prices[day], highestFrom[day + 1])
随后每个买入日只查询 highestFrom[buy + 1],保证卖出严格更晚。第二层枚举被后缀查询替代,时间降为
O(n),代价是保存 O(n) 的最高价数组。
这个数组中的相邻状态只服务于构造;最终扫描买入日时仍需要整份后缀,因为未来最高价位于尚未处理的方向。 若改为固定卖出日,所需的最低买入价来自已经扫描过的历史,可以边走边压缩为一个整数。
固定卖出日¶
扫描到卖出日 sell 时,合法买入日只能来自 [0, sell)。该日能得到的最佳利润为:
prices[sell] - min(prices[0..sell - 1])
prefixMinimumPrice 用 lowestEarlierPrice 维护这个前缀最小值。先以旧最低价计算当前卖出候选,再把当天
价格纳入最低价,保持“状态只包含严格更早日期”的含义。后缀数组和第二次扫描随之消失,工作空间降为常数。
状态走读¶
对 [9,4,7,2,8,5]:
卖出日价格 |
计算前历史最低价 |
当日候选利润 |
扫描后最大利润 |
更新后最低价 |
|---|---|---|---|---|
4 |
9 |
-5 |
0 |
4 |
7 |
4 |
3 |
3 |
4 |
2 |
4 |
-2 |
3 |
2 |
8 |
2 |
6 |
6 |
2 |
5 |
2 |
3 |
6 |
2 |
任意合法交易都有唯一卖出日。扫描到该日时,历史最低价对应一个真实且更早的买入日,产生的候选合法;它又 不高于任何其他买入价,所以覆盖该卖出日的全部交易。取所有卖出日候选的最大值即为全局最优。
排序与主解选择¶
不能把价格排序后用最大值减最小值,排序会丢失日期约束。[5,8,2] 的全局最低价 2 出现在最高价
8 之后,两者不能组成交易。
公开入口采用前缀最低价扫描,因为它在线性时间内同时保持时间顺序和最优历史买入价,且只需两个整数状态。
单天数组的循环不执行,初始利润 0 自然返回。
复杂度分析¶
下标对枚举时间 O(n²)、空间 O(1);后缀最高价方法时间 O(n)、空间 O(n);前缀最低价
主解时间 O(n)、额外空间 O(1)。所有方法只读取价格数组。