买卖股票的最佳时机
Best Time to Buy and Sell Stock
只允许买卖一次，返回能获得的最大利润；不能先卖后买。
在力扣中练习题目描述
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输入：prices = [7,6,4,3,1] 输出：0 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
1 <= prices.length <= 1050 <= prices[i] <= 104
解题思路
主解法
一次扫描 · 维护最低价
每天只问：如果今天卖，之前的最低买入价是多少
枚举“卖出日” i，最佳买入日一定是 i 之前价格最低的那天。于是扫描时维护两个量：
minPrice：到目前为止见过的最低价格；best：目前为止的最大利润。
每到一天，先用 p - minPrice 尝试更新 best，再把今天计入 minPrice（顺序反过来会让今天买入今天卖出，得到 0，不影响最优但逻辑不自然）。
分步图解
只能先买后卖。维护此前最低价，每天尝试用它买入、今天卖出。
自拟价格先跌到 1，再涨到 10。前半段 2 买 8 卖只有 6，真正的答案是 1 买 10 卖，利润 9。只记住当前最低价，就不会错过后面的更大涨幅。
分步图解
价格 7：最低价仍是 2；今天卖出收益 5，当前最大 6。
- profit
- 5
- best
- 6
时间 O(n)，空间 O(1)。
时间 O(n)空间 O(1)
易错点
- 先更新 minPrice 再算利润：当天买入当天卖出，利润恒为 0（虽然不影响最终 best，但逻辑错）。
- 把 minPrice 初始化成 0：会把 0 当成买入价，得到错误的更大利润。
- 只记录最大价格：最大价格可能出现在最低价格之前，交易顺序非法。
对照解法
暴力枚举 · 买卖日
枚举所有买入日和卖出日
结果正确，但 O(n²)；仅用于理解“一次扫描到底省掉了什么”。
两层循环枚举 i < j，计算 prices[j] - prices[i]，取最大值。
它天然保证先买后卖，但每对日期都检查一遍，数据量大时会超时。一次扫描的贪心正是把“之前的最低价”缓存下来，省掉内层循环。
- 1枚举买入日 i。
- 2枚举卖出日 j > i。
- 3更新最大利润。
时间 O(n²)空间 O(1)
易错点
- 内层从 i 开始：当天买卖利润 0，不影响结果但多做一次。
- 内层从 0 开始：可能算出先卖后买的非法交易。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
演示输入
prices = [9,2,8,3,7,1,6,10]只能先买后卖。维护此前最低价，每天尝试用它买入、今天卖出。
查看 C++ 代码
延伸阅读
- “之前的最低价”是典型的前缀最值，很多一次扫描题都靠维护一个前缀量把 O(n²) 降成 O(n)。
- 如果允许多次买卖，问题变成累加所有上涨区间，思路不同。