力扣这道121题我其实讲过很多遍了——不管是带新人入坑刷题还是公司内部做算法分享它永远是我拿来找手感的第一题。原因很简单表面看是个Easy难度的买卖股票问题背后却藏着一趟扫描 状态维护这个高频思考范式在力扣热题100里会反复出现。今天我就从贪心算法的视角把这道题彻底拆透从暴力解到最优解从边界条件到面试追问一次性讲明白。1. 先把题目读透买股票的关键不是预测未来1.1 题目回顾与核心约束题目表述很简短给定一个数组 pricesprices[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题的解法你的算法功底绝对差不到哪去。这种主动变形训练比刷十道同难度新题的价值要高得多。