BM80. 买卖股票的最好时机(一)
题目描述
给定数组 prices，prices[i] 是股票第 i 天的价格。 你可以买入一次、卖出一次，且买入必须在卖出之前的某一天。 求能获得的最大收益；如果不能获利，返回 0。
输入格式
prices：int 型一维数组，表示每一天的股票价格。
输出格式
返回 int 型，最大收益（不能获利则为 0）。
示例
示例 1
输入：
prices = [8,9,2,5,4,7,1]
输出：
5
说明： 第 3 天（价格 2）买入，第 6 天（价格 7）卖出，利润 7 - 2 = 5。
示例 2
输入：
prices = [2,4,1]
输出：
2
说明： 第 1 天（价格 2）买入，第 2 天（价格 4）卖出，利润 2。
示例 3
输入：
prices = [3,2,1]
输出：
0
说明： 价格单调下跌，无法获利，返回 0。
解题思路
第一步：理解问题本质
只能做「一次买入 + 一次卖出」，且买入在卖出之前。
等价于：找一对下标 i < j，使 prices[j] - prices[i] 最大。
第二步：暴力枚举
枚举买入日和卖出日，取最大差价：
best = 0
for i in range(n):
for j in range(i + 1, n):
best = max(best, prices[j] - prices[i])
O(n²)，思路直白但不够快。
第三步：一次遍历（贪心）
换个角度：固定卖出日 j，那么买入日当然选「j 之前价格最低的那天」。
于是只要从左到右扫一遍，边扫边维护「到目前为止的最低价 min_price」，
就得到「今天卖出的最大利润」prices[j] - min_price，再对所有 j 取最大。
用一个变量记住最低价，就把 O(n²) 降到了 O(n)。
完整代码实现
算法可视化 · 逐帧回放这道题的代码12 帧 · 录制输入 [8,9,2,5,4,7,1]
from typing import List
class Solution:
def maxProfit(self, prices: List[int]) -> int:
"""一次交易：维护历史最低价，更新最大利润"""
min_price = float('inf')
best = 0
for p in prices:
min_price = min(min_price, p) # 到当天为止的最低价
best = max(best, p - min_price) # 今天卖出的最大收益
return best
示例推演
以 prices = [8,9,2,5,4,7,1] 为例：
| 当天价格 p | min_price | 今天卖出的利润 p - min_price | best |
|---|---|---|---|
| 8 | 8 | 0 | 0 |
| 9 | 8 | 1 | 1 |
| 2 | 2 | 0 | 1 |
| 5 | 2 | 3 | 3 |
| 4 | 2 | 2 | 3 |
| 7 | 2 | 5 | 5 |
| 1 | 1 | 0 | 5 |
最终 best = 5，与答案一致。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 双重循环 | O(n²) | O(1) | 简单但慢 |
| 一次遍历 | O(n) | O(1) | 推荐 |
易错点总结
1. 先卖出再买入
题目要求买入在卖出之前，遍历时是「先更新 min_price，再算利润」， 不要反。
2. 忘记「不能获利返回 0」
best 初始化成 0 就能天然处理单调下跌的情况（利润永远为负，取 0）。
3. 用「最大值 - 最小值」图省事
直接取全局最大减全局最小是错的 —— 最大值可能出现在最小值左边， 违反了「先买后卖」。
扩展思考
- 允许无限次交易见 BM81. 买卖股票的最好时机(二)。
- 最多两笔交易见 BM82. 买卖股票的最好时机(三)。