LeetCode 剑指 Offer 63. 股票的最大利润
题目描述
题意分析
数组按时间先后记录股价，最多选择一天买入，再选择更晚的一天卖出，利润是卖出价减买入价。只允许这一笔交易；没有盈利机会时可以不交易，答案为 0。
解法：一次扫描维护最低买入价
核心思路
[!blue]
如果固定第
i天卖出，卖出价就已经确定，要让prices[i]-买入价最大，只需选取前i天中的最低价格。更贵的历史买入价不会对当前或任何未来卖出日更有利，因此不必保留所有买入候选。用
minPrice保存prices[0..i-1]的最低价，用ans保存此前所有卖出日能够取得的最大利润。处理第i天时，先以prices[i]-minPrice更新答案，再把当天价格纳入最低价，为下一个卖出日准备状态。这样每个卖出日都与它之前最优的买入日配对，所有合法交易都会被相同卖出日的候选覆盖；在这些候选中取最大值，就是全局最优利润。
ans初始为 0，亏损候选不会替换“不交易”的选择。
解题步骤
- 少于两天时无法完成先买后卖，直接返回 0，也避免读取空数组首项。
- 初始化
minPrice = prices[0]、ans = 0，从第二天开始扫描。- 用
prices[i]-minPrice更新ans，此时最低价只来自更早的日期。- 用
prices[i]更新minPrice，扫描结束后返回ans。价格一直下降时，每天的候选利润都为负；价格不变时，候选利润为 0，两种情况都返回 0。后来出现更低的买入价只会改善未来候选，不会抹去已经记录的历史最高利润。
代码实现
class Solution {
public int maxProfit(int[] prices) {
if (prices.length < 2) {
return 0;
}
int minPrice = prices[0];
int ans = 0;
for (int i = 1; i < prices.length; i++) {
// 先以历史最低价尝试卖出，再把当天价格提供给未来
ans = Math.max(ans, prices[i] - minPrice);
minPrice = Math.min(minPrice, prices[i]);
}
return ans;
}
}
func maxProfit(prices []int) int {
if len(prices) < 2 {
return 0
}
minPrice := prices[0]
ans := 0
for i := 1; i < len(prices); i++ {
// 先以历史最低价尝试卖出，再把当天价格提供给未来
if prices[i]-minPrice > ans {
ans = prices[i] - minPrice
}
if prices[i] < minPrice {
minPrice = prices[i]
}
}
return ans
}
复杂度分析
- 时间复杂度：$O(n)$，每天一次。
- 空间复杂度：$O(1)$，最低价与最优利润。
关键点总结
[!green]
- 历史最低与全局最低不同，未来低价不能用于此前卖出。
minPrice维护未来交易的买入候选，ans维护已经完成的最优交易，两个状态各有用途。- 一次交易只对应一个买卖差值，不能累加多个上涨段的收益。
易错点总结
[!yellow]
- 直接用全局最大减最小，可能让买入晚于卖出。
- 最低价初值零会虚构免费买入。
- 读取首项前未处理空输入，会越界。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 122. 买卖股票的最佳时机 II | 中等 | 本题只能完成一次交易，原题允许多次交易，可以累积不同上涨段。 |
| 123. 买卖股票的最佳时机 III | 困难 | 把一次交易扩展为最多两次，需要分别保存每次买入卖出状态。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！