0121. Best Time to Buy and Sell Stock
=====================================
题目信息
--------
:题号: 0121. 买卖股票的最佳时机
:难度: Easy
:主题: 数组、下标对枚举、前缀最小值、单次扫描
:原题: `LeetCode 0121 `_
:重点: 固定交易一端后删除另一端的重复搜索,再把后缀数组压缩为扫描中的历史最低价
题目重述
--------
给定整数数组 ``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++ 实现
--------
.. code-block:: cpp
#include
#include
class Solution {
private:
int enumerateTransactions(const std::vector& prices) {
int maximumProfit = 0;
for (int buy = 0; buy < static_cast(prices.size()); ++buy) {
for (int sell = buy + 1; sell < static_cast(prices.size()); ++sell) {
maximumProfit = std::max(maximumProfit, prices[sell] - prices[buy]);
}
}
return maximumProfit;
}
int suffixMaximumPrices(const std::vector& prices) {
const int count = static_cast(prices.size());
std::vector 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& prices) {
int lowestEarlierPrice = prices[0];
int maximumProfit = 0;
for (int sell = 1; sell < static_cast(prices.size()); ++sell) {
maximumProfit = std::max(maximumProfit, prices[sell] - lowestEarlierPrice);
lowestEarlierPrice = std::min(lowestEarlierPrice, prices[sell]);
}
return maximumProfit;
}
public:
int maxProfit(std::vector& prices) {
return prefixMinimumPrice(prices);
}
};
题解
----
交易下标对
~~~~~~~~~~
原始搜索空间是所有满足 ``buy < sell`` 的下标对。``enumerateTransactions`` 固定买入日后枚举所有更晚卖出日,
恰好检查每笔合法交易一次;``maximumProfit`` 从 ``0`` 开始,使全部价差非正时选择不交易。
长度为 ``n`` 时共有 ``n(n - 1) / 2`` 个候选,时间为 ``O(n²)``。每次价差计算很便宜,瓶颈是对不同买入日
反复寻找其右侧的最高价格,或对不同卖出日反复寻找其左侧的最低价格。
固定买入日
~~~~~~~~~~
若买入日 ``buy`` 已定,最佳卖出价就是严格位于其后的最高价格。``suffixMaximumPrices`` 从右向左预处理:
.. code-block:: text
highestFrom[day] = max(prices[day], highestFrom[day + 1])
随后每个买入日只查询 ``highestFrom[buy + 1]``,保证卖出严格更晚。第二层枚举被后缀查询替代,时间降为
``O(n)``,代价是保存 ``O(n)`` 的最高价数组。
这个数组中的相邻状态只服务于构造;最终扫描买入日时仍需要整份后缀,因为未来最高价位于尚未处理的方向。
若改为固定卖出日,所需的最低买入价来自已经扫描过的历史,可以边走边压缩为一个整数。
固定卖出日
~~~~~~~~~~
扫描到卖出日 ``sell`` 时,合法买入日只能来自 ``[0, sell)``。该日能得到的最佳利润为:
.. code-block:: text
prices[sell] - min(prices[0..sell - 1])
``prefixMinimumPrice`` 用 ``lowestEarlierPrice`` 维护这个前缀最小值。先以旧最低价计算当前卖出候选,再把当天
价格纳入最低价,保持“状态只包含严格更早日期”的含义。后缀数组和第二次扫描随之消失,工作空间降为常数。
状态走读
~~~~~~~~
对 ``[9,4,7,2,8,5]``:
.. list-table::
:header-rows: 1
* - 卖出日价格
- 计算前历史最低价
- 当日候选利润
- 扫描后最大利润
- 更新后最低价
* - 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)``。所有方法只读取价格数组。