LeetCode 121 买卖股票的最佳时机——一文搞懂贪心算法思想

LeetCode 121 买卖股票的最佳时机——一文搞懂贪心算法思想

前言

很多人第一次接触贪心算法时都会有一个疑问：

什么叫贪心？

事实上，LeetCode 121《买卖股票的最佳时机》就是最经典的贪心入门题。

这道题没有复杂的数据结构，也不需要动态规划，只需要维护两个变量，就能在一次遍历中求出最大利润。

通过这篇文章，你将彻底理解：

• 什么是贪心思想
• 为什么一次遍历就能解决问题
• 为什么要记录历史最低价格
• 如何分析时间复杂度与空间复杂度

一、题目描述

给定一个数组prices。

其中：

prices[i]

表示第i天的股票价格。

你只能进行一次交易：

• 买入一次
• 卖出一次

并且必须：

先买后卖

求能够获得的最大利润。

如果无法获得利润，则返回：

0

示例1

prices=[7,1,5,3,6,4]

输出：

5

解释：

第2天价格1买入 第5天价格6卖出 利润 = 6 - 1 = 5

示例2

prices=[7,6,4,3,1]

输出：

0

解释：

价格持续下跌 不交易最优

二、最容易想到的方法

很多人第一反应是：

枚举买入日。

再枚举卖出日。

例如：

foriinrange(n):forjinrange(i+1,n):profit=prices[j]-prices[i]

计算所有可能利润。

然后取最大值。

时间复杂度

两层循环：

O(n²)

如果：

n=100000

就会超时。

因此需要更高效的方法。

三、核心贪心思想

观察题目。

假设今天价格是：

6

如果决定今天卖出。

那么什么时候买最划算？

答案一定是：

今天之前价格最低的那一天。

因为：

利润 = 卖出价格 - 买入价格

想让利润最大：

• 卖出价格尽量高
• 买入价格尽量低

而卖出价格已经固定为今天。

所以只需要知道：

历史最低价格

即可。

四、维护两个变量

整个遍历过程中只需要维护：

1. 历史最低价格

min_price

表示：

到当前为止出现过的最低价格

相当于最佳买入点。

2. 最大利润

max_profit

表示：

目前为止能够获得的最大收益

五、遍历时做什么？

对于每一天：

假设当前价格：

price

需要做两件事。

第一步：计算今天卖出的利润

如果今天卖出：

profit=price-min_price

如果利润更大：

max_profit=max(max_profit,profit)

第二步：更新历史最低价格

看看今天是不是更便宜：

min_price=min(min_price,price)

如果是。

以后买入就选今天。

六、完整执行过程模拟

示例：

prices=[7,1,5,3,6,4]

初始化

min_price=+∞ max_profit=0

第1天

价格：

7

利润：

7-∞

无意义。

最大利润：

0

更新最低价：

min_price=7

第2天

价格：

1

利润：

1-7=-6

最大利润不变：

0

更新最低价：

min_price=1

第3天

价格：

5

利润：

5-1=4

更新：

max_profit=4

最低价保持：

1

第4天

价格：

3

利润：

3-1=2

小于4。

不更新。

第5天

价格：

6

利润：

6-1=5

更新：

max_profit=5

第6天

价格：

4

利润：

4-1=3

不更新。

最终结果：

5

七、完整代码实现

fromtypingimportListclassSolution:defmaxProfit(self,prices:List[int])->int:min_price=float("inf")max_profit=0forpriceinprices:# 今天卖出的利润profit=price-min_price# 更新最大利润ifprofit>max_profit:max_profit=profit# 更新历史最低价格ifprice<min_price:min_price=pricereturnmax_profit

八、代码优化写法

利用 Python 内置函数：

fromtypingimportListclassSolution:defmaxProfit(self,prices:List[int])->int:min_price=float("inf")max_profit=0forpriceinprices:max_profit=max(max_profit,price-min_price)min_price=min(min_price,price)returnmax_profit

逻辑完全一致。

代码更简洁。

九、为什么这是贪心算法？

贪心思想核心：

每一步都选择当前最优决策。

本题中：

对于每一天。

都选择：

历史最低价格作为买入点

因为这一定能让当天卖出的利润最大。

不需要回头修改之前的选择。

因此符合贪心策略。

十、高频易错点

1. 直接用全局最大值减全局最小值

错误思路：

max(prices)-min(prices)

例如：

[5,4,3,2,1]

得到：

5-1=4

但实际上：

5出现在1前面 无法先卖后买

答案应该是：

0

2. min_price初始化为0

错误：

min_price=0

会导致：

profit=price-0

相当于0元买股票。

明显不合理。

正确：

float("inf")

3. 返回负利润

题目要求：

亏损时不交易

因此答案最小只能是：

0

4. 使用双层循环

虽然能做出来。

但复杂度：

O(n²)

无法通过大数据测试。

十一、复杂度分析

时间复杂度

只遍历一次数组：

O(n)

空间复杂度

只使用两个变量：

O(1)

十二、总结

这道题是贪心算法最经典的入门题。

核心思想可以总结为一句话：

遍历每一天，记录历史最低价格；假设今天卖出，计算利润并更新最大收益。

整个过程中维护两个变量：

• min_price：历史最低价格
• max_profit：当前最大利润

最终仅需一次遍历即可得到答案。

掌握本题后，建议继续练习：

• LeetCode 122 买卖股票的最佳时机Ⅱ
• LeetCode 55 跳跃游戏
• LeetCode 45 跳跃游戏Ⅱ
• LeetCode 860 柠檬水找零

这些题目都是贪心算法中的经典案例。