企业官网建设流程全解析

买卖股票的最佳时机在力扣上属于那种“看着简单，动手就懵”的经典题。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变成 1，max_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 = inf，max_profit = 0
• 第1天 price=7：7 < inf，所以min_price = 7；7 - 7 = 0，max_profit = 0
• 第2天 price=1：1 < 7，所以min_price = 1；1 - 1 = 0，max_profit仍为 0
• 第3天 price=5：5 > 1，不更新min_price；5 - 1 = 4，max_profit更新为 4
• 第4天 price=3：3 > 1，不更新；3 - 1 = 2，不超过 4，保持 4
• 第5天 price=6：6 > 1，不更新；6 - 1 = 5，超过 4，max_profit = 5
• 第6天 price=4：4 > 1，不更新；4 - 1 = 3，不超过 5，保持 5

最终返回 5。整个过程min_price停留在 1，因为后续再也没有比 1 更低的价格；max_profit在遍历到第 5 天时被更新为 5，之后再没有遇到更高利润。

这个手推过程建议每个人都在纸上画一遍。特别是处理类似[3,2,6,1,4]这种“最低点出现在后半段”的用例时，手推能让你看清楚，即使最后一天才出现最低价 1，也不影响最大利润 4（2买入、6卖出）被正确算出来。

3.2 我在本地调试时踩过的坑

第一个坑是min_price初始化为0。如果初始化为 0，碰到[7,1,5,3,6,4]这种所有价格都是正数的用例时，第一次循环price < min_price不成立，因为 7 > 0，min_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 用哪些测试用例验证代码

写完代码后，我强烈建议至少跑这几组测试：

第六个用例空数组在力扣上不会出现，但本地测试时如果你用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(i+1, len(prices))，那无论如何都是 O(n^2)。换成一次遍历的贪心即可。另外检查一下是不是在循环里反复调用了len(prices)或切片操作，Python 的切片会创建新列表，代价很大，尽量用下标访问。

5.4 面试时如何口述这道题

如果是面试，我建议这样组织表达：先说明暴力法能解但复杂度高，再自然引出 “我们需要在一次遍历中同时维护两个变量：历史最低价和当前最大利润”。然后用题目示例走一遍过程，最后给出代码并分析复杂度。面试官一般还会追问“为什么不用买卖多次”，这时候就可以说因为题目限定一次交易，所以我们只需要找到最低的买入点和最高的卖出点，但必须保证卖出日在买入日之后。

5.5 一个提升刷题效率的小技巧

我在刷力扣时，会准备一个“题解模板”笔记，把同类型的题目归类。比如“股票买卖”这一组，我会从 121 题开始，先用贪心解决，再写 DP 对比，然后把变体依次刷完。刷完之后总结成一张表，记录状态定义、转移方程、初始化和复杂度。这样复习的时候一目了然，面试前也能快速过一遍。

最后再分享一个我个人的操作习惯：拿到题目后，不要急着写代码，先在注释或者笔记本上写下三个东西：输入是什么、输出是什么、约束条件是什么。然后想清楚最暴力的做法，再考虑优化。121题就是典型的“暴力→贪心”两步跳，如果你能在一分钟内写出正确的贪心代码，说明你确实理解了，而不是背住了答案。