力扣这道121题，我其实讲过很多遍了——不管是带新人入坑刷题，还是公司内部做算法分享，它永远是我拿来"找手感"的第一题。原因很简单：表面看是个Easy难度的买卖股票问题，背后却藏着"一趟扫描 + 状态维护"这个高频思考范式，在力扣热题100里会反复出现。今天我就从贪心算法的视角，把这道题彻底拆透：从暴力解到最优解，从边界条件到面试追问，一次性讲明白。
1. 先把题目读透：买股票的关键不是预测未来
1.1 题目回顾与核心约束
题目表述很简短：给定一个数组 prices，prices[i] 表示某支股票第 i 天的价格。你只能选择某一天买入，并在之后的某一天卖出，求能获得的最大利润。如果无法获得利润，返回 0。
这里有两条关键约束，不少新手第一眼会忽略：
- 只能完成一笔交易：买了之后只能卖一次，不能反复买卖。
- 必须先买后卖：卖出日必须严格晚于买入日。这条约束决定了你不能"事后诸葛亮"地找全局最小值和全局最大值。
很多新手一上来就想"这不就是 max(prices) - min(prices) 吗？"然后开心地提交，结果在[4, 3, 2, 1]这种用例上直接翻车。为什么？因为最低价 1 在数组最后一天，它之前的价格全比它高，按照规则你不可能先以 1 买入、再把之前更高的价格卖出。这就是经典的"后视镜陷阱"：你站在今天回头看，价格走势一清二楚，但问题设定的场景是你每天只能依据"过去和当下"做决策，看不见未来。
1.2 它为什么是力扣热题100里的"开场菜"
121题被放在热题100很靠前的位置，不是因为它最容易混过，而是因为这一道题同时踩中了两个核心算法思想的节拍。
第一个是动态规划的降维思想。很多人不知道，121题实际上是动态规划极简化的产物。股票题目家族的完整解法往往需要二维状态DP，比如"持有/不持有"两个状态，甚至还要再加交易次数维度。但121题因为限制"只能交易一次"，所有状态可以被压缩成两个变量：历史上的最低买入价、历史上的最大利润。当你以后做到122题（无限次交易）、123题（最多两次交易）、309题（带冷冻期）时，就会发现状态变量像积木一样一个个加回来。所以121题是理解整个股票题谱系的总纲。
第二个是贪心算法的精髓：**每一步都做当下最优选择，最终收敛到全局最优解。**在这道题里，当下的最优选择就是"只维护历史最低价"。你不需要预测未来价格会不会更低，因为如果未来真的有更低的价格，它会自动成为新的历史最低价；如果未来没有更低价格，那你手里的历史最低价就是最佳买入点。这个"以不变应万变"的思路，比"每次都试图预测走势"的直觉要可靠得多。
2. 从暴力解到贪心解：为什么一趟扫描就够
2.1 先写暴力解：双重循环的朴素起点
我建议每个初学的人先亲手写一遍暴力解。这个步骤看起来"浪费"，实际是理解问题复杂度最直观的方式。
from typing import List class Solution: def maxProfit(self, prices: List[int]) -> int: n = len(prices) max_profit = 0 for i in range(n): # 枚举买入日 for j in range(i + 1, n): # 枚举卖出日（必须在买入之后） profit = prices[j] - prices[i] if profit > max_profit: max_profit = profit return max_profit思路非常朴素：枚举所有买入点 i，再枚举它之后的所有卖出点 j，算出每一对组合的利润，不断更新最大值。时间复杂度 O(n²)，空间复杂度 O(1)。
当数组长度来到 10^5（力扣的常规测试规模），暴力解要跑 10^10 次操作，Python 必超时。所以暴力解只能拿来验证正确性，不能作为最终提交的答案。
但写暴力解的过程中，你会注意到一个规律：对于固定的卖出日 j，只有买入日 i 在[0, j-1]区间内取到最低价时，利润才最大。换句话说，枚举卖出日 j 时，我们根本不需要遍历所有可能的 i，只需要知道前 j-1 天的最低价。这个观察就是通往贪心解的钥匙。
2.2 贪心选择的正确性论证
现在来论证为什么"维护历史最低价"是安全且最优的贪心策略。
核心是一个数学事实：假设我们在第 j 天卖出，那么这天的最大利润必然是
profit_j = prices[j] - min(prices[0..j-1])
也就是当天的价格，减去买入日之前所有天里的最低价。这个式子里没有依赖任何未来信息，它只是穷举了"第 j 天之前所有可能的买入日"后得到的最优值。
整个问题的答案就是：
max_profit = max(profit_j)，其中 j 取 1 到 n-1
如果你直接按这个式子写代码，会发现似乎需要 O(n²) 的时间。但有个关键优化：min(prices[0..j-1])是可以递推维护的。我们定义一个变量 min_price，在从左往右扫描的过程中不断被更小的价格更新。这样在第 j 天，min_price 天然就是[0, j-1]区间的最小值，不需要回头重算。
这就是为什么最终解法只需要一趟扫描，原因是"历史最小值"这个信息量可以被压缩成一个变量，随时递推、随时取出。
说它是贪心，是因为每一步迭代只做一个局部决策：把 min_price 更新为当前看到的最低价。这个选择不会牺牲未来的任何收益，因为：
- 如果未来价格更低，min_price 会继续被更新；
- 如果未来价格更高，由于 min_price 已是历史最低，用它买入获得的利润一定不低于用其他历史价格买入的利润。
不存在"为了贪当下的最优而错失未来更优解"的情况，所以这个贪心策略是安全的，也是可证明最优的。
3. Python实现与逐步拆解
3.1 最终解法：一趟扫描的贪心实现
这是我个人最推荐的标准写法，代码短、逻辑清晰、边界稳：
from typing import List class Solution: def maxProfit(self, prices: List[int]) -> int: if not prices: return 0 min_price = prices[0] # 截至当前天，历史最低买入价 max_profit = 0 # 历史最大利润，注意初始化为 0 for price in prices[1:]: # 先尝试更新历史最低价 if price < min_price: min_price = price # 再计算当天卖出能获得的利润 current_profit = price - min_price # 更新历史最大利润 if current_profit > max_profit: max_profit = current_profit return max_profit逐行解释一下：
if not prices: return 0：防御空数组。力扣的测试用例里一定有prices = []，不判空直接访问prices[0]会当场 IndexError。min_price = prices[0]：把第一天的价格作为初始历史最低价，这是最自然的起点。- 循环从
prices[1:]开始，因为第 0 天不可能卖出（还没买入）。 - 循环体里先更新最低价，再计算利润。这里存在一个面试常问的细节：如果
price比min_price还低，那么current_profit = 0，而此时max_profit至少是 0，所以"当天更新最低价后立刻卖出"不会污染结果。这个顺序是安全的。
还有另一种常见写法，用float('inf')做初始值：
min_price = float('inf') max_profit = 0 for price in prices: max_profit = max(max_profit, price - min_price) min_price = min(min_price, price) return max_profit这种写法把"更新利润"放在"更新最低价"前面，所以即使第一天也能正确计算，不需要单独处理prices[0]。两种思路都对，但面试时别中途切换写法——同一个逻辑循环里换来换去最容易引入 bug。
3.2 边界条件与防御性编程
我反复跟人说，边界条件不是加分项，是必拿分项。121题最容易被测到的边界情况有下面这些，每个都应该在心里过一遍：
| 输入 | 期望输出 | 原因 |
|---|---|---|
[] | 0 | 空数组，无法交易 |
[7] | 0 | 只有一天，不能买后再卖 |
[7, 6, 4, 3, 1] | 0 | 严格递减，任何买入都会亏，选择不交易 |
[3, 3, 3] | 0 | 价格持平，无利润 |
[1, 2, 3, 4] | 3 | 第 0 天买入，最后一天卖出 |
[7, 1, 5, 3, 6, 4] | 5 | 经典用例，第 1 天买、第 4 天卖 |
[3, 2, 6, 5, 0, 3] | 4 | 注意全局最小值 0 在末尾，但实际最优解是 2 买入、6 卖出 |
注意表格里那个[3, 2, 6, 5, 0, 3]，这是最容易麻痹大意的用例。如果你直接max(prices) - min(prices)，会算出 6，但正确利润是 4。这就是我前面反复说的"后视镜陷阱"——最低点出现在数组倒数第二天，往前没有更高的卖出价能与之匹配。
4. 力扣实测踩过的坑：三个高频错误与性能表现
4.1 最容易踩的三个坑
这道题虽然标着 Easy，但我带过的人里至少半数会踩到下面某个坑。写题的时候留意一下，能省不少调试时间。
坑一：把"最大利润"写成"全局最大值减全局最小值"
这个错误前面已经分析过，本质是忽略了"必须先买后卖"这一时间约束。我见过有人提交前还信誓旦旦地说"时间复杂度 O(n)，肯定是最优解"，结果被一个简单用例打回原形。记住：这道题求的不是价格差绝对值的最大值，而是"有序对差值"的最大值——卖出索引必须大于买入索引。
坑二：max_profit 初始化错误
有人习惯把所有求最大值的变量初始化为float('-inf')，但这道题允许不交易，利润下界是 0。如果初始化为负无穷，在[7, 6, 4, 3, 1]这种全亏场景下，返回值就会是负数，直接 Wrong Answer。所以max_profit必须初始化为 0，语义是"最差我就选择不交易"。
坑三：维护额外数组导致空间复杂度退化
我还见过一种写法：先用一遍扫描构建"前缀最小值数组"，再遍历一遍计算利润。时间复杂度同样是 O(n)，但空间复杂度从 O(1) 退化成了 O(n)。力扣的数据规模下不会超内存，但如果面试官追问"能否优化空间"，你就得绕回双变量的写法。既然一趟扫描同时能完成"更新最低价"和"计算利润"，就没必要引入额外数组。
4.2 大输入量下的性能实测
我用 Python 在本地做过实测，随机生成长度 10^5、价格在 0 到 10^4 之间的数组，上面贪心解法的运行时间大约在 40 到 50 毫秒，内存占用约 17 MB。这个表现在力扣上基本属于击败 90% 以上的提交，不用担心性能问题。
对比一下，暴力解在同样数据量下需要约 5×10^9 次循环，本地跑完至少几分钟，力扣平台上直接超时。所以在这道题里，贪心解不是"优化技巧"，而是"唯一可行解"。
如果你想在本地跑 LeetCode 的 Python 代码，有件小事容易被忽略：环境里可能没装typing模块，或者 Python 版本过低导致List[int]类型注解解析失败。建议本地直接用python3命令运行，并在文件开头加上from typing import List，别让环境问题干扰你做算法验证。
5. 从121题延伸：面试追问的三种方向与刷题路线建议
5.1 面试官视角：秒杀这道题之后的加码提问
121题本身不足以评判算法水平，但它是极佳的试金石。面试官看到你轻松解出后，通常会立刻加码。根据我的经验，追问基本沿着三条线展开。
追问一：允许无限次交易怎么办？
这就是力扣122题，贪心解法依然简洁漂亮：只要今天的价格比昨天高，就认为昨天买入、今天卖出能赚，把所有"正差价"累加起来。
from typing import List class Solution: def maxProfit(self, prices: List[int]) -> int: total = 0 for i in range(1, len(prices)): if prices[i] > prices[i - 1]: total += prices[i] - prices[i - 1] return total这个解法的直观理解是"不放过任何一个上涨波段"。它的贪心本质是：局部正收益一定要拿到，局部负收益绝对不扛。和121题对比，121题限制只能吃一个波段，所以要找跨度最大的那一段；122题允许无限次买卖，所以把每一小段上涨全部加起来即可。
追问二：最多交易两次怎么办？
对应力扣123题，难度直接跳到 Hard。此时单纯贪心已经不够，需要上动态规划。状态设计大致是四个变量，分别表示"第一次买入后手上的资金"“第一次卖出后手上的资金"“第二次买入后手上的资金"“第二次卖出后手上的资金"。你会发现，多一次交易限制，状态就从两个变量膨胀到四个。这正是我前面强调的：学121题要理解"状态记录"的本质，才能平移到更复杂的题目上。
追问三：卖出后带冷冻期怎么办？
对应力扣309题，卖出后要等一天才能再次买入，这需要二维 DP（持有/不持有两个状态）来建模，贪心策略已经没法直接套用。这类变形题非常适合检验一个人是"背了模板"还是"真正理解了状态转移"。
5.2 刷题路线定位：121题之后该刷什么
如果你正按力扣热题100刷题，我的建议是刷完121之后按下面的顺序继续：
- 122题（买卖股票的最佳时机II）：理解贪心累加思路，和121形成对照。
- 714题（买卖股票的最佳时机含手续费）：每笔交易扣掉手续费，理解成本如何影响贪心决策。
- 123题（买卖股票的最佳时机III）：从两个变量到四个变量的状态扩展。
- 188题（买卖股票的最佳时机IV）：把交易次数参数化为 k，写出通用 DP。
- 309题（最佳买卖股票时机含冷冻期）：用状态机 DP 处理复杂规则约束。
如果时间有限，至少要做122和714。这两道题做透之后，你对"贪心什么时候适用、什么时候必须上DP"会建立非常清晰的判断力。
5.3 我的个人体会：刷题不要图快，要图"能变形"
最后说一点带私货的体会。我见过太多人刷力扣的目的是"AC 就完事"——代码跑通，截图发个朋友圈，然后永远封存这道题。这种刷法在简单题上损失不大，但到中等和困难题上就暴露问题了：背了一堆套路，题目条件稍微一变就手足无措。
121题最值得咀嚼的，不是那几行代码，而是这个思考过程：扫描到当前位置时，我只需要维护哪些变量，就能保证最终答案正确？min_price和max_profit两个变量背后，是对"第 j 天卖出的最优买入日，必然是历史最低价"这一规律的提炼。这个规律放到任何一个"前缀极值"类问题上都适用——比如"接雨水""最大子数组和"，它们共享同一个底层思路：一趟扫描，维护一个"到当前位置为止的最优子信息"，再用当前元素尝试更新全局答案。
我的建议是，刷完121后别急着跳下一题，自己动手改一改条件。把"只能买一次"改成"最多买两次"，推导一遍；把"卖出后必须等一天才能再买入"加进去，再推导一遍。如果真能徒手推出123题的解法，你的算法功底绝对差不到哪去。这种主动变形训练，比刷十道同难度新题的价值要高得多。
