LeetCode 121. 买卖股票的最佳时机
题目描述
题意分析
prices[i]表示第i天的股票价格。最多完成一次买入和一次卖出，且卖出日必须晚于买入日，求能获得的最大利润。允许不交易，因此没有盈利机会时返回0。不能直接用全局最高价减全局最低价，因为最高价可能出现在最低价之前；也不能累加多段上涨收益，那会相当于进行了多次交易。题目保证价格数组非空，只有一天时无法完成交易，答案为
0。
解法：一次遍历维护历史最低价
核心思路
[!blue]
直接枚举买入日和卖出日需要检查许多组合。换个角度，先固定卖出日：当天卖价已经确定，要让利润最大，只需选择此前价格最低的一天买入。其他更贵的买入日不会带来更好的结果，因此不必逐个保存。
从左到右扫描，用
minPrice记录当前卖出日之前的最低价，用maxProfit记录已经考察过的所有卖出日能得到的最大利润。第一天只能作为买入候选，所以初始化minPrice = prices[0]，从第二天开始枚举卖出日。处理当天时，先用
prices[i] - minPrice计算当天卖出的最好利润，并与已有答案取最大值。随后再把当天价格纳入minPrice，供之后的卖出日使用。这个顺序使每次计算利润时，最低价都来自严格更早的日期。更新出更低的买入价，不会抹掉以前已经得到的利润：
minPrice只影响今后的交易候选，maxProfit独立保留历史最优值。每个合法交易都有一个卖出日，而每个卖出日的最佳买入价都被检查过，所以扫描结束后的最大值就是全局最优利润。将
maxProfit初始化为0，表示可以选择不交易。后续只取更大的利润，因此持续下跌、价格不变或只有一天时，都会正确返回0。
解题步骤
- 初始化历史最低价
minPrice = prices[0]，最大利润maxProfit = 0。- 从第二天开始，将当天价格作为卖出价，用它减去
minPrice，更新maxProfit。- 再令
minPrice取自身与当天价格的较小值，使它包含截至当天的最低价。- 遍历所有可能的卖出日后，返回
maxProfit。
代码实现
class Solution {
public int maxProfit(int[] prices) {
int minPrice = prices[0];
// 允许不交易，零收益不会被负利润覆盖。
int maxProfit = 0;
for (int i = 1; i < prices.length; i++) {
// 先按今天卖出计算利润，此时最低价只来自过去。
maxProfit = Math.max(maxProfit, prices[i] - minPrice);
// 计算完利润，再把今天纳入后续日期的历史最低价。
minPrice = Math.min(minPrice, prices[i]);
}
return maxProfit;
}
}
func maxProfit(prices []int) int {
// 允许不交易，零收益不会被负利润覆盖。
minPrice, maxProfit := prices[0], 0
for _, price := range prices[1:] {
// 先按今天卖出计算利润，此时最低价只来自过去。
if profit := price - minPrice; profit > maxProfit {
maxProfit = profit
}
// 计算完利润，再把今天纳入后续日期的历史最低价。
if price < minPrice {
minPrice = price
}
}
return maxProfit
}
复杂度分析
- 时间复杂度：$O(n)$，每个价格只处理一次。
- 空间复杂度：$O(1)$，只使用两个变量。
关键点总结
[!green]
- 固定卖出日后，只需维护它之前的最低价格，无需枚举所有买卖组合。
- 先计算利润、再更新最低价，买入日始终早于卖出日。
- 利润初始为 0；全程下跌时不交易。
易错点总结
[!yellow]
- 直接用全局最高价减全局最低价，可能违反先买后卖的顺序。
- 将
minPrice初始化为 0，会把不存在的 0 元买入价算进答案。- 累加每段上涨利润解决的是可多次交易的 122 题，不是本题。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 122. 买卖股票的最佳时机 II | 中等 | 本题只能完成一次交易，原题允许多次交易，可以累积不同上涨段。 |
| 123. 买卖股票的最佳时机 III | 困难 | 把一次交易扩展为最多两次，需要分别保存每次买入卖出状态。 |
| 188. 买卖股票的最佳时机 IV | 困难 | 以持有状态和交易次数描述每天的最优收益；本题只允许一次买卖，该题推广到 k 笔交易。 |
| 309. 买卖股票的最佳时机含冷冻期 | 中等 | 以持有状态和交易次数描述每天的最优收益；本题只允许一次买卖，该题卖出后增加冷冻限制。 |
| 714. 买卖股票的最佳时机含手续费 | 中等 | 以持有状态和交易次数描述每天的最优收益；本题只允许一次买卖，该题在交易转移时计入手续费。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！