力扣121买卖股票最佳时机：贪心算法与Python实现详解

力扣121题“买卖股票的最佳时机”我愿称之为股票系列的开胃菜也是力扣热题100里的常客。很多刷题的人对这道题又爱又恨爱是因为它看起来简单恨是因为简单背后藏着贪心、动态规划两种经典解法的思想碰撞。我当初第一次刷这道题时满脑子都是“找最小值和最大值不就行了吗”结果一提交就发现自己天真了——你找到全局最大值也没用因为最大值可能出现在最小值前面股票交易可不允许你穿越回去买入。今天这篇文章我把这道题的贪心解法给你掰开揉碎讲清楚顺手送你一套可以直接“抄作业”的Python模板以及我刷题过程中踩过的坑和总结的排查思路。无论你是刚接触算法的初学者还是正在准备面试、想系统刷力扣的求职者这篇文章都值得你花几分钟读完。1. 题目到底在问什么先别急着写代码很多朋友拿到这道题的第一反应就是打开编辑器开始写for循环这其实是个好习惯但在此之前我更建议你先花两分钟把题面读透。只有把题目真正理解到位后面的解法才能顺理成章而不是靠背模板。1.1 题面拆解一次买入、一次卖出题目给定一个数组 prices 其中 prices[i] 表示股票在第 i 天的价格。你只能选择某一天买入然后在未来某一天卖出要求计算出能获得的最大利润。这里的约束条件有几个关键信息值得注意只能交易一次也就是一次买入加一次卖出不能卖了再买。买入必须在卖出之前。比如第3天买入最早只能在第4天卖出不能当天买当天卖有的变种题允许当天买卖这题默认不允许但实际上当天买卖没有意义因为买卖价格相同利润为0。如果不能获得任何正利润也就是价格一路下跌那最大利润就是0而不是负数。换句话说你可以选择不交易。咱们把这道题放到真实场景里类比一下。假设你看中了一只股票但你没有买入它的历史价格你只有一个未来价格的预测列表。你自然希望在价格最低的那天买入在之后价格最高的那天卖出这样收益最大。但难点在于你不知道哪天是最低价——因为价格是一天一天揭晓的你只能在已经走过的日子里找答案。这个“只能看过去不能看未来”的约束就是这道题的灵魂所在。它排除了一种错误的直觉解法先找到整个数组的最小值和最大值然后直接相减。因为最小值可能在最大值后面这种跨时间的交易是无效的。理解了这一层你再看接下来要讲的贪心解法就会觉得它是那么自然而合理。1.2 这道题为什么配得上贪心算法这个标签“贪心算法”这四个字看起来很高大上其实核心思想就一句话每一步都做出当前看起来最好的选择期望最终结果是全局最优的。放在这道题里贪心体现在两个方面第一遍历到第 i 天时我们记住前 i-1 天里价格最低的那一天。这件事的成本极低只需要一个变量不断更新但它保证了“买入点”永远是历史最优的。第二在每一天计算“如果我今天卖出能赚多少钱”也就是当前价格减去历史最低价然后维护这个差值的最大值。你可能会问这个做法每一步选的都是“局部最优”凭什么最终结果就是“全局最优”这个问题的答案是因为题目限制只能交易一次我们从最低点买入、在后面某一天卖出这个交易结构本身决定了收益只取决于两个因素——买入价格和卖出价格。只要我们在遍历过程中不断用“历史最低价”作为候选买入点那么任何可能的“卖在更高点”的方案都会被我们枚举到。换句话说最优的方案一定满足“买入价是历史最低价”这个条件所以用贪心逐步更新是不会漏掉最优解的。这也是为什么这道题虽然也可以用动态规划解但贪心是更简洁、更符合直觉的方案。理解了“为什么贪心可行”比你背十遍代码都管用。2. 从暴力到贪心完整思考过程分享我第一次面对这道题的时候脑子里冒出来的解法其实是暴力遍历。别笑很多刚从学校出来的朋友第一反应跟我一样。暴力解法的思路毫无技巧枚举所有可能的买入日和卖出日计算它们的差价取最大值。这里我先把暴力解法的代码贴出来虽然它不会通过大数据量的测试用例但它是理解后续优化的重要跳板。def maxProfit(prices): 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这个解法的时间复杂度是O(n²)空间复杂度是O(1)。当数组长度很小的时候它完全没问题但一旦给到你几万条价格数据两层循环就会变得非常吃力。力扣的判题系统中这道题的数组长度最高可达10⁵O(n²)的算法必然超时。那优化从哪里入手呢如果你仔细观察暴力解法里重复做的事情就会发现一个规律对于每一个卖出日 j我们其实只需要知道 0 到 j-1 天中出现过的最低价格用它作为潜在买入点就够了。为什么要遍历所有 i因为更高的买入价格一定不会产生更大的利润我们没必要为同一个卖出日尝试所有历史买入点只需要记住最小的那一个即可。这就是贪心策略的核心在遍历过程中始终维护一个变量记录“已经遇到过的最小价格”然后计算当前价格与这个最小价格的差值更新最大利润。于是代码从两层循环变成了单层循环时间复杂度从O(n²)降到了O(n)。你可能会在这个地方产生一个疑惑这种“只维护历史最小值”的做法会不会错过某些场景下的最优解比如某一天价格不是历史最低但它之后涨得更多是不是应该在那一天买入我们说这不会因为任何有效方案都必须买入在前、卖出在后。如果某一天价格不是历史最低意味着在此之前有更低的买入点。在相同的卖出日下用更低的买入价一定获得更高的利润。所以我们只需要锁定“截至当前的最低买入价”这一个候选就足够了所有更优的方案都会在这个候选买入价的基础上产生。这就是贪心在这道题里成立的根本原因。它不是玄学而是建立在“买入价越低越好”这个单调关系之上的。想明白这一点你对贪心算法的理解就不再停留在“背模板”的阶段了。3. Python实现与细节精讲从代码到逐行分析聊完思路接下来是你们最关心的问题代码怎么写。我先把完整代码放出来这段代码已经通过力扣的判题测试可以直接用当然我建议你先自己理解一遍然后再动手敲进编辑器里跑一跑。def maxProfit(prices): 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很多初学者看到这段代码第一反应是就这对就这。但越是精简的代码越考验你对每个细节的把控。下面对代码逐行拆解。初始化部分min_price 设置为正无穷大max_profit 设置为0。为什么 min_price 要设置成正无穷而不是 prices[0] 或者一个很大的数因为正无穷可以保证循环第一次执行时price min_price 一定成立从而顺利把第一个元素赋给 min_price。如果你设置成 prices[0]那也没问题但需要单独处理数组为空的情况设置成正无穷则天然免疫数组为空的边界条件即使 prices 是空列表返回值也是0不会报错。循环体内的逻辑是这道题的精髓。每一轮迭代我们做两个判断第一个判断当前价格是否刷新历史最低价。如果刷新了就更新 min_price。注意这一步不需要同时计算利润因为“当天买入当天卖出”没有意义利润为0和维护 max_profit 的初始值没有区别。这里我用的是 if 而不是 if-else 的变体严格来说写成两个 if 也是对的但用 elif 可以保证在同一天不会先更新最低价、再以这个新低点卖出算一笔0利润让逻辑更清晰。第二个判断当前价格减去历史最低价看能不能刷新最大利润。这一步其实就是模拟“如果在今天卖出我能赚多少钱”。因为最低价是历史最优买入点所以这个差值就是截至今天能获得的最大利润。我建议你拿一个具体的例子手推一遍这个过程。假设 prices [7, 1, 5, 3, 6, 4]第1天价格7min_price从inf变为7max_profit保持0。第2天价格11 7min_price变为1max_profit还是0。第3天价格55不小于1计算5-14max_profit更新为4。第4天价格33不小于1计算3-12不大于4max_profit保持4。第5天价格66不小于1计算6-15max_profit更新为5。第6天价格44不小于1计算4-13不大于5max_profit保持5。最终返回5对应第2天买入价格1、第5天卖出价格6的利润完全正确。再测一个典型的下行数组 prices [7, 6, 4, 3, 1]第一天7min_price变成7max_profit保持0。第二天6min_price变成6profit0max_profit还是0。第三天4min_price变成4profit0。第四天3min_price变成3profit0。第五天1min_price变成1profit0。返回0。这对应题目要求不能获得正利润时返回0选择不交易。代码看完了我还要多提一嘴“为什么先更新最低价、再更新最大利润”的顺序。有的朋友可能会写成先算 profit 再更新 min_price这也没问题。但如果反过来你在同一天先更新了 min_price 为当天的更低价格再用这个更低价格去做利润计算那得到的利润是0或者一个错误的“当天买卖”值。虽然不会影响最终结果因为0小于任何正利润但这个逻辑瑕疵在面试时被追问会比较尴尬。我建议代码顺序就保持上面写的那样先检查是不是新低如果不是新低再尝试更新利润思路清清楚楚。4. 实际刷题中的常见问题与排查技巧代码写出来了但你真正在力扣上刷题时可能会遇到一些细节问题。有的是边界条件处理不当有的是对题目理解有偏差还有的是面试中面试官突然追问“为什么贪心是对的”把你问懵了。下面我把这些高频问题整理成一张速查表并附上我的排查思路和独家心得。4.1 常见问题速查表问题现象原因分析解决方法空数组返回报错直接访问 prices[0] 初始化 min_price用 float(inf) 初始化或先判断数组长度单元素数组返回错误循环逻辑不完整没有处理无法交易的情况单元素数组利润必然为0代码天然返回0结果输出负数把不交易的情况也算成负收益max_profit 初始化为0保证不交易时返回0超时用了双层循环暴力求解改用贪心单次遍历 O(n)与动态规划解法搞混对贪心和动归的边界认识不清理解本题贪心可行是因为“一次交易买入价越低越好”4.2 min_price 初始值到底怎么选我在刷题群里经常看到有人问min_price 能不能初始化成 prices[0]答案是能但你要多写几行防御代码。如果用 prices[0]你需要先判断数组是否为空否则会抛出索引越界异常。用 float(inf) 则完全不用管这些这是力扣解题里非常常见的一个技巧在后续很多题目中都能用到。不过有一点要注意有些变种题目会要求你返回具体的买入日和卖出日而不只是最大利润。这时候 float(inf) 初始化的方式仍然适用但你需要额外记录更新 min_price 时的下标以及更新 max_profit 时的区间。这属于121题的延伸建议你把基础版本吃透后再去挑战。4.3 面试时如何回答面试官的连环追问刷题最终还是要服务于面试所以我特别想分享一点面试经验。面试官考这道题时通常不会满足于“你会写贪心解法”这个结果他更想看到你完整的思维链路。我建议你按这个顺序展示思路先说出暴力解法枚举所有买入卖出时间对O(n²)这是最朴素的思路。再指出暴力解法的瓶颈重复枚举了大量不可能产生最优解的买入点。然后自然地引出贪心因为买入价越低利润越高所以我们只需要维护历史最低价。最后补充正确性证明任何最优方案中买入日一定是卖出日之前的最低价否则可以替换成更低的买入价获得更高利润。按照这条链路走下来面试官会认为你不仅会写代码还具备分析问题和沟通方案的能力。这比闷头直接把代码甩出来要好太多。5. 从121题出发贪心和动态规划的边界你分清楚了吗聊到这里肯定有朋友会问我看网上很多题解是用动态规划写的跟贪心有什么区别哪个更好这是刷题绕不开的一个问题尤其是股票系列有好几道题理解清楚算法之间的边界能帮你举一反三。先说说本题的动态规划解法。定义 dp[i] 表示第 i 天卖出能获得的最大利润那么递推关系是dp[i] max(dp[i-1], prices[i] - min_price)其中 min_price 是前 i 天的最低价。这个递推的意思是要么第 i 天不卖沿用前一天的利润要么第 i 天卖出利润是当前价格减去历史最低价。把这个动态规划的空间优化一下你会发现一个惊人的事实dp 数组根本不需要保留只需要维护一个 dp 的“滚动最大值”也就是我们贪心解法里的 max_profit。也就是说这道题用贪心写出来的代码本质上就是动态规划空间优化后的形式。那么什么时候必须用动态规划、不能用贪心呢答案是当交易次数变成变量时。比如122题允许无限次交易贪心依然有效——你只需要把每段上涨的利润都累加起来就行。但到了123题“最多买卖两次”以及188题“最多买卖k次”贪心就失效了因为局部最优的多次买卖可能互相冲突必须用动态规划在“交易次数”这个维度上做状态转移。所以你可以在自己的知识体系里这样理解贪心是这道题最精简的解法而动态规划是股票系列的通法模板。当题目约束越少、交易结构越简单时贪心就越可能直接命中答案一旦题目加了次数限制、冷冻期、手续费这些变数动态规划才是那个能兜底的工具。5.1 最容易上手的扩展122题为什么贪心更简单122题和121题唯一的区别是你可以尽可能多地完成交易也就是在价格低点买入、高点卖出可以交易很多次。这道题的贪心解法堪称艺术def maxProfit(prices): profit 0 for i in range(1, len(prices)): if prices[i] prices[i - 1]: profit prices[i] - prices[i - 1] return profit核心思想是只要今天比昨天价格高就认为昨天买入、今天卖出是一次有效交易把所有上涨波段的差额加起来。因为不限交易次数所以每一次上涨都不能放过。代码比121题还短但第一次看懂的人往往会被它的简洁震惊到。我强烈建议你把121题和122题放在一起对比学习这两道题能帮你把“一次交易”和“无限次交易”的贪心策略彻底区分开理解这两个问题之后你再去刷123题就不会那么痛苦了。5.2 从股票系列看刷题的方法论最后说点题外话。很多朋友刷题喜欢按“题号顺序”一路往下刷但我的体会是按“专题”刷效率更高。股票系列就是一个非常好的专题121题一次交易122题无限次交易123题两次交易188题k次交易309题带冷冻期714题带手续费。把这一系列放在一起你能清晰地看到算法复杂度是如何一步步升级的也能更好地理解贪心、动态规划各自的适用边界。如果你决定按这个路线刷我建议你每做完一道题都写一下题解笔记不用多详细哪怕只是在代码注释里写一句“这题和121题的区别是什么”都行。我自己刷题时有个习惯每完成一个专题就强迫自己不看代码、用文字叙述一遍解题思路。这个方法让我对题目的理解远远超过看十遍题解。写在最后的小技巧我实际刷这道题时最大的体会是代码本身没有难度难的是说服自己“贪心为什么是对的”。如果你某天在面试现场或者刷题群里被人问住了不必慌张把问题拉回到最基础的场景里想一遍——只允许买卖一次那么任何一天的卖出利润都等于当前价格减去此前的历史最低价而历史最低价是随着遍历不断被更新和发现的。想通了这一层121题就真的是你的囊中之物了。另外还有一个我自己踩过的坑想分享给你初学Python的时候我总喜欢用 max() 函数去更新最大利润写出来是 max_profit max(max_profit, price - min_price)这当然是对的。但力扣判题系统对运行时间的统计很敏感这种写法跟手动 if 判断相比性能几乎没差别所以你按自己的喜好来就行不用刻意追求极致优化。真正重要的是你把这道题的思路吃透形成肌肉记忆下次遇到类似问题能条件反射地想到“遍历时维护历史最优值”这个模式这才是刷题最大的收获。