题目描述
只能选某天买入、之后某天卖出(各一次)，求最大利润。
prices = [7, 1, 5, 3, 6, 4]
输出 = 5 （第2天买1，第5天卖6）
思路解析
只要记住「今天之前出现过的最低价」minPrice，今天卖的利润就是 price − minPrice。一路取最大值就行，O(n) 一遍搞定。
第 0 天 · 价 7：第一天，最低价就是 7（紫色 l 标最低价位置），还没法卖，利润 0。
第 1 天 · 价 1：价格 1 比之前的最低价还低，更新 minPrice=1。最低价指针 l 移到这里。
第 2 天 · 价 5：今天卖能赚 5 − 1 = 4。刷新最大利润为 4。minPrice 不变。
第 3 天 · 价 3：今天卖只赚 2，没超过 4，最大利润不变。
第 4 天 · 价 6 ⭐：今天卖能赚 6 − 1 = 5！刷新最大利润 5（绿色标出买/卖点）。
第 5 天 · 价 4：今天卖只赚 3，不超过 5。
结束：走完一遍，最大利润 5。全程只用一个 minPrice 和一个 profit 变量。
「维护一个目前为止的最值」是数组题超常用的套路：最大子数组、接雨水都有它的影子。
参考代码（Python）
Python
1def maxProfit(self, prices):
2 minPrice = float(class="cl-str">"inf")
3 profit = 0
4 for p in prices:
5 minPrice = min(minPrice, p) # 更新历史最低价
6 profit = max(profit, p - minPrice) # 今天卖能赚多少
7 return profit复杂度分析
- 时间复杂度：O(n) —— 只扫一遍
- 空间复杂度：O(1) —— 两个变量
套路模板
一遍扫描里维护「历史最值」，再用它和当前元素算答案——很多一维最优问题都能套。
Python
1best = 初始; extreme = 第一个
2for x in arr:
3 extreme = min(extreme, x) # 历史最优(看题改 min/max)
4 best = max(best, x - extreme) # 用当前和历史最优算答案易错点
- ❌ 先算利润再更新最低价 → ✅ 先更新 minPrice，再算利润（保证「买在卖之前」）
- ❌ profit 初值设成很大的数 → ✅ profit 初值设 0(不交易也合法)（不存在正利润时返回 0）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。