002 · Best Time to Buy and Sell Stock
My First Thoughts
最开始会把它理解成“找最大增幅”：从某一天买入，在之后某一天卖出，利润就是后面的价格减去前面的价格。这里有一个很关键的限制：必须先买后卖，所以差值不是简单的全局 max - min，而是有顺序要求的最大增幅。
最直接的解法还是遍历。从第一个元素出发，枚举它之后的所有价格，计算差值；每一轮都保留所有可能利润，最后选出最大值。如果最大值是负数，就返回 0，否则返回那个最大利润。
def max_profit(prices: list[int]) -> int:
best = 0
n = len(prices)
for buy in range(n):
for sell in range(buy + 1, n):
best = max(best, prices[sell] - prices[buy])
return best这当然能得到正确答案，因为它检查了每一种先买后卖的可能。
进一步想，其实不需要真的把每一个差值都保存下来。每一轮只保留当前见过的最大利润即可，本质上相当于一边计算一边提前比较。
换句话说，所有合法组合大概是 \(A(n, 2)\) 个，我们是在这些组合里算差值，再求最大值。
Why That Is Not Enough
问题是复杂度太高。prices.length 最大可以到 \(10^5\)，两层循环会变成 \(O(n^2)\)，很容易超时。
接着我想到一个更激进的方向：既然是找最大差值，那能不能先算出极差，也就是全局 max - min？
如果全局最小值在全局最大值前面，那么这个极差就是答案。但如果顺序不合法，就尝试围绕全局最大值和全局最小值切分：
- 找到最大值的 index，看它前面区间的最小值，得到差值
a - 找到最小值的 index，看它后面区间的最大值，得到差值
b - 最后比较
a和b
这个思路看起来是在修正全局极差的顺序问题，但它仍然不可靠。原因是：最优解不一定使用全局最大值，也不一定使用全局最小值。
例如：
prices = [10, 7, 1, 9, 0, 5]全局最大值是 10，全局最小值是 0，但它们的顺序不合法。真正的最大利润是 1 -> 9，利润为 8。
如果只围绕全局最大值和全局最小值切一次，就可能得到 0 -> 5 的利润 5，从而漏掉中间的 1 -> 9。
所以这题不能只看全局极差，也不能只围绕全局 max 和 min 做局部修正。它必须尊重时间顺序，并且在最坏情况下需要扫描全部元素。
Final Idea
遍历到某一天时，如果今天卖出，那么最好的买入价格一定是今天之前出现过的最低价格。
因此只需要维护两个变量：
min_price：到当前为止见过的最低价格best：到当前为止能得到的最大利润
从第二天开始，每看一个价格 price：
- 先尝试用
price - min_price更新最大利润 - 再用
price更新历史最低价格
Why It Works
对任意一天来说，卖出日已经固定为今天。要让利润最大，买入日只能从今天之前选择，而最佳买入日就是过去价格最低的那一天。
所以我们不需要保存所有过去价格，也不需要枚举所有组合。只要在遍历过程中保存“过去最低价”，就已经保留了今天卖出所需的全部历史信息。
Code
def max_profit(prices: list[int]) -> int:
min_price = prices[0]
best = 0
for i in range(1, len(prices)):
price = prices[i]
best = max(best, price - min_price)
min_price = min(min_price, price)
return bestComplexity
| Time | \(O(n)\) — 每个价格只看一次 |
| Space | \(O(1)\) — 只维护两个变量 |
Takeaway
当题目要求在有顺序约束的数组里找最大差值时，不要急着找全局
max - min。先固定当前位置作为“卖出点”，再问：如果今天卖，过去最好的买入价是什么？遍历时维护一个历史最低价，就能把所有合法组合压缩成一次扫描。
← Quiz