LeetCode 121 · 买卖股票的最佳时机：一次遍历，记住最低价就够了
这道题是股票系列的第一题，也是最简单的一题——只允许交易一次。虽然简单，但它奠定了一个核心思路：“遍历到第 i 天时，我只需要知道之前的最小值”。这个"只关心历史最优"的思想贯穿了整个股票系列。
题目长什么样
给定一个数组prices，prices[i]表示第i天的股票价格。你只能选择某一天买入，并在未来的某一天卖出。计算你能获取的最大利润。如果不能获利，返回0。
输入：prices = [7,1,5,3,6,4]
输出：5
说人话就是：找一个最低点买入、之后的最高点卖出，算最大差价。注意买入必须在卖出之前。
第一反应：两层循环暴力枚举
最直接的想法——枚举每一对买入/卖出日期，找最大差值。
classSolutionBrute:defmaxProfit(self,prices:List[int])->int:max_profit=0foriinrange(len(prices)):forjinrange(i+1,len(prices)):profit=prices[j]-prices[i]ifprofit>max_profit:max_profit=profitreturnmax_profit| 维度 | 值 | 说明 |
|---|---|---|
| 时间 | O(n²) | n 最大 10^5，铁定超时 |
| 空间 | O(1) |
暴力法的问题很明显：对于每一天，我们都重新扫描了它后面的所有天。但实际上，当我站在第i天卖出时，我只需要知道之前哪天最便宜就行了，不需要再枚举所有可能的买入日。
最优解：一次遍历，维护历史最低价
思路非常简单：
遍历每一天的价格： - 如果今天的价格比历史最低价还低 → 更新最低价（今天适合买入） - 否则 → 计算今天卖出的利润（今天价格 - 历史最低价），更新最大利润classSolution:defmaxProfit(self,prices:List[int])->int:min_price=prices[0]max_profit=0forpriceinprices[1:]:ifprice<min_price:min_price=priceelifprice-min_price>max_profit:max_profit=price-min_pricereturnmax_profit为什么这样做是对的？
关键观察：最大利润 = 某天的价格 - 之前某天的最低价格。
当我们遍历到第i天时，min_price记录了prices[0]到prices[i-1]的最小值。那么prices[i] - min_price就是以第i天为卖出日能获得的最大利润。我们只需要在所有天数中取最大值即可。
这里用了一个贪心的思想：不需要记住在哪天买入，只需要记住最低价是多少。
跑一遍示例 1
prices = [7, 1, 5, 3, 6, 4] Day 0: min_price = 7, max_profit = 0 (初始化) Day 1: price = 1 1 < 7 → 更新 min_price = 1 min_price=1, max_profit=0 Day 2: price = 5 5 > 1, profit = 5 - 1 = 4 > 0 → 更新 max_profit = 4 min_price=1, max_profit=4 Day 3: price = 3 3 > 1, profit = 3 - 1 = 2 < 4 → 不更新 min_price=1, max_profit=4 Day 4: price = 6 6 > 1, profit = 6 - 1 = 5 > 4 → 更新 max_profit = 5 min_price=1, max_profit=5 Day 5: price = 4 4 > 1, profit = 4 - 1 = 3 < 5 → 不更新 min_price=1, max_profit=5 最终: max_profit = 5 (Day 1 买入, Day 4 卖出)跑一遍示例 2
prices = [7, 6, 4, 3, 1] Day 0: min_price = 7 Day 1: 6 < 7 → min_price = 6 Day 2: 4 < 6 → min_price = 4 Day 3: 3 < 4 → min_price = 3 Day 4: 1 < 3 → min_price = 1 全程没进过 elif 分支 → max_profit = 0 (无法盈利)| 维度 | 值 | 说明 |
|---|---|---|
| 时间 | O(n) | 一次遍历 |
| 空间 | O(1) | 只用了两个变量 |
两种解法放在一起看
| 解法 | 时间 | 空间 | 思路 |
|---|---|---|---|
| 暴力枚举 | O(n²) | O(1) | 枚举所有买入/卖出对 |
| 一次遍历 | O(n) | O(1) | 维护历史最低价，贪心更新最大利润 |
暴力法的冗余在于：对每个卖出日，都重新遍历了之前的所有买入日。而实际上之前的最小值只需要一个变量就能维护——这就是 O(n²) 到 O(n) 的优化。
这道题教会我什么
"只需要知道历史最优"是一个通用模式
这道题的核心操作是price - min_price。我们不需要知道min_price出现在第几天，不需要知道之前的完整价格走势，只需要一个数字——历史最低价。
这种"只关心历史最优/最值"的模式在很多题目里都能看到：
- 最大子数组和（LeetCode 53）：只关心以当前位置结尾的最大和
- 爬楼梯（LeetCode 70）：只关心前两步的方案数
- 股票系列后续题目：维护不同的状态变量
贪心：每一步做局部最优选择
这道题是贪心算法的典型案例。我们没有尝试所有可能的交易组合，而是在每一天做一个简单的决策：今天的价格是否足以刷新最大利润？如果是，就更新；如果不是，就跳过。因为题目只允许一次交易，所以这个贪心策略是正确的。
边界：价格一直下跌
当价格单调递减时，max_profit始终为 0，代码自动处理了这种情况。不需要额外判断——因为elif分支永远不会进入，max_profit保持初始值 0。这也是为什么初始值设为 0 而不是负无穷的原因。
完整测试代码
fromtypingimportListclassSolution:defmaxProfit(self,prices:List[int])->int:min_price=prices[0]max_profit=0forpriceinprices[1:]:ifprice<min_price:min_price=priceelifprice-min_price>max_profit:max_profit=price-min_pricereturnmax_profitif__name__=="__main__":s=Solution()prices=[7,1,5,3,6,4]print(f"输入:{prices}, 输出:{s.maxProfit(prices)}")prices=[7,6,4,3,1]print(f"输入:{prices}, 输出:{s.maxProfit(prices)}")prices=[2,4,1]print(f"输入:{prices}, 输出:{s.maxProfit(prices)}")prices=[3]print(f"输入:{prices}, 输出:{s.maxProfit(prices)}")prices=[1,2]print(f"输入:{prices}, 输出:{s.maxProfit(prices)}")相关题目推荐：
- LeetCode 122 · 买卖股票的最佳时机 II（允许多次交易，贪心/DP）
- LeetCode 123 · 买卖股票的最佳时机 III（最多两次交易，状态机 DP）
- LeetCode 53 · 最大子数组和（同样的"维护历史最优"思想）