买卖股票的最佳时机在力扣上属于那种“看着简单动手就懵”的经典题。121题标的是简单难度但它的解法覆盖了贪心、动态规划、差分数组好几条路径很多人在第一次接触时都会绕进“找最高点和最低点”的误区里结果代码写出来要么超时要么在边界用例上翻车。这次我就拿这道题当例子把贪心算法的思路、Python实现、测试设计和同类题扩展一次讲透适合刚入坑力扣的Python刷题党也适合准备面试想快速梳理套路的人。1. 题目到底在问什么先别急着写代码1.1 原题描述与输入输出题目给你一个数组prices其中prices[i]表示第i天这支股票的价格。你最多只能选择某一天买入并在之后的某一天卖出求你能获得的最大利润。如果无论如何都无法获得正利润就返回 0。输入[7,1,5,3,6,4]时答案是 5因为在第 2 天价格 1买入第 5 天价格 6卖出利润为 5。注意这里买入必须在卖出之前不能同一天先卖后买也不能当天买当天卖除非利润为0但通常利润至少为0。我见过不少人第一次看到这个题目时的第一反应是找最小值买入找最大值卖出两者相减就是答案。这个直觉对了一半但有一个致命问题最大值可能出现在最小值之前。比如[7, 5, 3, 1]最小值是 1最大值是 7但如果先买 7 再卖 1那是亏的所以全局最大利润并不是简单的最大值减最小值。1.2 为什么暴力解是死路最容易想到的暴力思路是双层循环外层模拟买入日内层模拟卖出日计算所有可能交易的利润取最大值。这个思路正确性没问题但是时间复杂度是 O(n^2)。当prices长度达到 10^5 甚至更大时提交到力扣上基本会超时。我在实际刷题时测过prices长度为 10^5 时Python 的双层循环大概要跑好几秒力扣的时限通常给到 1 秒或 2 秒所以 O(n^2) 方案基本可以放弃。就算你优化成用max(prices[j] - prices[i])的列表推导式底层还是双层循环只是写法上看起来简单了一点复杂度没有本质变化。1.3 顺着时间轴“边走边看”的贪心思想那怎么把复杂度降到 O(n) 呢关键是要意识到我们在遍历每一天的时候实际上只需要关心两个变量——到目前为止出现的最低价格以及如果把股票卖在当天能获得的利润。想象你是一个操盘手每天收盘时记录两件事一是历史最低买入价二是“如果我今天卖出能赚多少”。这个利润算出来之后和历史最大利润比较一下取更大的那个。整个过程只需要一次从左到右的扫描不需要回头再看之前的数据。这就是贪心算法的雏形每一步只做当前看起来最优的选择并且这个局部最优能推出全局最优。具体来说假设当前遍历到第 i 天价格是prices[i]在此之前我们已经知道历史最低价min_price那么今天的潜在利润就是prices[i] - min_price。因为买入日一定在今天之前这个差值已经保证了“先买后卖”的顺序。如果这个差值比之前算出来的最大利润还大就更新最大利润。然后再把今天的价格和min_price比较如果今天价格更低就更新min_price因为更低的买入价能让我们在之后的卖出中获利更多。这种“记录历史最低点”的做法之所以是贪心是因为它每一步都基于当前信息做出局部最优决策买入价当然越低越好所以每次遇到更低价就更新利润当然越高越好所以每次算出更高的利润就更新。这个决策链条不需要回溯不需要考虑未来价格完全符合贪心算法的“无后效性”特征。2. Python 代码实现与逐行拆解2.1 最精简的贪心写法直接上代码这是力扣上最常见的 Python 解法之一class Solution: def maxProfit(self, prices: List[int]) - int: min_price float(inf) max_profit 0 for price in prices: # 更新历史最低价 if price min_price: min_price price # 计算当天卖出能获得的利润 elif price - min_price max_profit: max_profit price - min_price return max_profit我见过有人把elif写成if功能上其实也没有问题因为如果price min_price说明今天价格比之前所有天都低那么price - min_price必然等于 0 或负数不会超过max_profit初始为 0所以用两个独立的if也可以。但用elif能让逻辑更清晰要么更新最低点要么计算利润避免做无意义的减法。注意这里min_price初始化成了float(inf)。为什么不直接取prices[0]从功能上说两种做法都可以但float(inf)有个好处即使prices为空你也不需要额外判断数组长度循环体内第一次迭代时price min_price一定成立min_price会被正确赋值为第一个元素。如果直接用prices[0]碰到空数组就直接索引越界了。当然力扣上这道题给的prices长度至少为 1但养成用float(inf)初始化最小值的习惯在别的场景下能省去很多边界判断。2.2 用min和max让代码更简洁如果你喜欢函数式写法可以这样改写class Solution: def maxProfit(self, prices: List[int]) - int: min_price float(inf) max_profit 0 for price in prices: min_price min(min_price, price) max_profit max(max_profit, price - min_price) return max_profit这个版本更短但每次循环都要调用两次函数性能上会比条件判断版本稍微慢一点点。在 LeetCode 这种数据规模下差别可以忽略但在追求极致性能的面试场景里建议还是用if判断的版本也更容易向面试官解释清楚每一步的意图。2.3 复杂度与边界条件分析时间复杂度显然是 O(n)因为只遍历了一次prices。空间复杂度 O(1)只用了一个min_price和一个max_profit变量。边界条件需要思考这么几种prices [7,6,5,4]一路下跌min_price会不断更新但price - min_price永远为 0 或负数所以max_profit保持 0返回 0符合题意。prices [1]只有一个元素循环一次min_price变成 1max_profit还是 0返回 0。prices [2, 1]第一天价格 2第二天价格 1。第二天更新min_price为 1但利润是 0不能因为第二天价格低就卖在第一天先卖后买不允许所以最终利润 0。这个用例最容易暴露“找全局最大最小值然后相减”的漏洞值得多写几遍。2.4 这段代码背后的贪心证明为什么局部最优就是全局最优面试时如果被问到“为什么贪心算法能得到正确答案”你需要能给出简单的逻辑证明。假设最大利润对应的是在第 i 天买入、第 j 天卖出i j。那么当遍历到第 j 天时min_price记录的一定是所有 i ≤ j 天中的最低价所以min_price ≤ prices[i]于是prices[j] - min_price ≥ prices[j] - prices[i]。也就是说当遍历到最优卖出日时我们计算出来的利润不会小于那个真实的最大利润因此最终max_profit一定能捕获到最优解。这层证明听起来有点绕但其实就是一句话任何时候历史最低价一定不高于最优方案里的买入价所以用历史最低价去卖出现有价格利润一定不少于任何其他之前的买入方案。3. 实操过程从暴力到贪心的完整演进3.1 手推示例用[7,1,5,3,6,4]走一遍我习惯在编辑器里手动模拟一遍循环过程这样对逻辑会有更直观的感受。假设输入是[7,1,5,3,6,4]初始min_price infmax_profit 0第1天 price77 inf所以min_price 77 - 7 0max_profit 0第2天 price11 7所以min_price 11 - 1 0max_profit仍为 0第3天 price55 1不更新min_price5 - 1 4max_profit更新为 4第4天 price33 1不更新3 - 1 2不超过 4保持 4第5天 price66 1不更新6 - 1 5超过 4max_profit 5第6天 price44 1不更新4 - 1 3不超过 5保持 5最终返回 5。整个过程min_price停留在 1因为后续再也没有比 1 更低的价格max_profit在遍历到第 5 天时被更新为 5之后再没有遇到更高利润。这个手推过程建议每个人都在纸上画一遍。特别是处理类似[3,2,6,1,4]这种“最低点出现在后半段”的用例时手推能让你看清楚即使最后一天才出现最低价 1也不影响最大利润 42买入、6卖出被正确算出来。3.2 我在本地调试时踩过的坑第一个坑是min_price初始化为0。如果初始化为 0碰到[7,1,5,3,6,4]这种所有价格都是正数的用例时第一次循环price min_price不成立因为 7 0min_price仍然是 0后续算出来的利润会变成5 - 0 5看起来奇迹般地没问题。但如果价格里出现了更小的正数比如[2,1]初始 0 会导致min_price始终是 0第二天计算1 - 0 1错误地返回 1。所以初始化一定要给一个“比所有可能价格都大”的数最常用的就是float(inf)如果你习惯用prices[0]也可以但需要额外处理空数组。第二个坑是在循环里先更新min_price还是先计算利润。假设你先更新min_price再计算price - min_price那在第一天价格就是最低点时利润永远是 0这没问题。但如果你先计算利润再更新min_price比如for price in prices: max_profit max(max_profit, price - min_price) min_price min(min_price, price)这在逻辑上其实也可以因为第一天price - inf永远是负数不会影响max_profit。但顺序不同会影响代码的可读性。我个人建议先更新最低价再算利润因为这样思路更自然“先确保手里有一个历史最低买入价再看今天卖出划不划算”。第三个坑是返回值。有人会想如果没有交易是不是返回-1题目明确要求返回 0表示不能获得正利润。因为你可以选择不买不卖利润为 0。所以max_profit初始值必须是 0而不是一个很小的负数。3.3 用哪些测试用例验证代码写完代码后我强烈建议至少跑这几组测试测试用例说明期望输出[7,1,5,3,6,4]题目标准样例5[7,6,4,3,1]单调递减无正利润0[1,2,3,4]单调递增最低点买入最高点卖出3[2,1]第二天价格低于第一天不能先卖后买0[1]只有一天0[]空数组如果本地测试0第六个用例空数组在力扣上不会出现但本地测试时如果你用prices[0]初始化就会直接崩溃用float(inf)则不会。这也是我建议用float(inf)的另一个理由。我一般会在本地用pytest写参数化测试或者干脆在main里构造一个用例列表批量调用maxProfit输出结果看一眼。力扣不支持直接调试所以本地跑通后再粘贴到编辑器里可以大幅提高通过率。3.4 力扣提交时的环境细节力扣的 Python 版本现在默认是 Python 3你提交代码时不需要导入List但类型提示需要你在代码开头加上from typing import List否则本地执行可能会报名称错误。在力扣编辑器里系统已经预置了导入但如果你复制到本地调试记得补上这一行。还有一点类名必须是Solution方法名必须是maxProfit参数名无所谓但变量名建议写清楚。力扣的测试程序会直接实例化Solution并调用maxProfit所以类和方法的名字不能改。4. 从这道题看贪心算法与动态规划的关系4.1 为什么这道题也可以用动态规划做121题除了贪心还有动态规划的经典解法。状态定义是dp[i][0]表示第 i 天结束时不持有股票的最大利润dp[i][1]表示第 i 天结束时持有股票的最大利润。转移方程dp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i]) dp[i][1] max(dp[i-1][1], -prices[i])注意这里dp[i][1]的转移很特殊因为整个交易只能买卖一次所以“持有股票”意味着在之前的某一天买入了买入花费是-prices[某天]。为了最大化持有时的利润我们应该让买入成本最低所以第 i 天持有股票的最大利润就是历史最低价的负数。这个转移方程本质上就是在做“记录历史最低点”的事情。最后答案是dp[n-1][0]即最后一天不持有股票的最大利润。你会发现如果把动态规划的空间压缩掉只保留前一天的状态它就退化成贪心版本了。实际上这道题的贪心解法就是动态规划的空间优化版本只不过状态转移太简单直接变成了两个变量。4.2 贪心和 DP 的适用边界很多初学者会纠结什么时候用贪心什么时候用动态规划。我的经验是如果每一步的局部最优能直接推导出全局最优并且不存在需要“回顾重新决策”的情形优先考虑贪心如果当前选择会影响未来的决策或者状态之间存在依赖关系就要用 DP。121题的特殊性在于交易次数限制为 1 次所以“历史最低价”这个信息是完备的贪心足够。但一旦交易次数变成 2 次或者加入冷冻期、手续费贪心就不太容易直接给出正确解这时 DP 会更清晰。这也说明刷题不能只会背题解要理解每道题为什么适合某个算法。4.3 同一道题的五种变体建议顺着刷力扣把买卖股票形成了一个系列我建议按顺序刷一遍会对状态转移有更深刻的理解121题只能交易一次。贪心或 DP 均可。122题可以交易多次每次卖出后可以再次买入。用贪心也很简单只要第二天价格比今天高就累加差值也可以用 DP但状态变为“当天持有或不持有”。123题最多两笔交易。这个就必须用 DP 了因为状态里要记录交易次数贪心很难处理。188题最多 k 笔交易。DP 升级。309题卖出后第二天不能买入冷冻期。DP 状态更复杂。714题每次交易有手续费。DP 转移时要把手续费减去。刷这些变体时你会发现 121 题学到的“记录历史最低价”思路是基础中的基础。122 题甚至可以理解为把所有上涨的坡度都收集起来。比如[1,2,3]每天都能赚 1总利润 2这本质上是把[1,2]和[2,3]两段上涨拼起来等于第1天买、第3天卖。5. 常见问题排查与刷题习惯速查5.1 为什么我的代码返回了负数如果你把max_profit初始化为一个很小的负数比如-10**9但是题目要求最低利润是 0因为可以选择不交易。所以初始化一定是 0。如果出现负数检查一下是不是把price - min_price直接返回了而没有和 0 取最大值。5.2 为什么用变量名max_profit会报错不会报错但注意不要和内置函数max冲突。如果你写了max ...后面再调用max(...)就会报TypeError: int object is not callable。我一开始经常犯这个错。养成习惯变量名尽量用max_profit、min_price不要覆盖内置函数。5.3 遇到超时怎么办如果提交超时先检查是不是用了 O(n^2) 的暴力解。有些人可能写了for i in range(len(prices)): for j in range(i1, len(prices))那无论如何都是 O(n^2)。换成一次遍历的贪心即可。另外检查一下是不是在循环里反复调用了len(prices)或切片操作Python 的切片会创建新列表代价很大尽量用下标访问。5.4 面试时如何口述这道题如果是面试我建议这样组织表达先说明暴力法能解但复杂度高再自然引出 “我们需要在一次遍历中同时维护两个变量历史最低价和当前最大利润”。然后用题目示例走一遍过程最后给出代码并分析复杂度。面试官一般还会追问“为什么不用买卖多次”这时候就可以说因为题目限定一次交易所以我们只需要找到最低的买入点和最高的卖出点但必须保证卖出日在买入日之后。5.5 一个提升刷题效率的小技巧我在刷力扣时会准备一个“题解模板”笔记把同类型的题目归类。比如“股票买卖”这一组我会从 121 题开始先用贪心解决再写 DP 对比然后把变体依次刷完。刷完之后总结成一张表记录状态定义、转移方程、初始化和复杂度。这样复习的时候一目了然面试前也能快速过一遍。最后再分享一个我个人的操作习惯拿到题目后不要急着写代码先在注释或者笔记本上写下三个东西输入是什么、输出是什么、约束条件是什么。然后想清楚最暴力的做法再考虑优化。121题就是典型的“暴力→贪心”两步跳如果你能在一分钟内写出正确的贪心代码说明你确实理解了而不是背住了答案。