题目链接#

LeetCode 121. 买卖股票的最佳时机

题目描述#

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。 设计一个算法来计算你所能获取的最大利润。

如果你不能获取任何利润，返回 0。

解法：贪心#

这题最直接的思路就是贪心。

对于每一天的价格 prices[i] 来说，如果今天决定卖出，那么最好的买入时机一定是：

前面所有天里价格最低的那一天。

所以遍历数组时，我们只需要维护一个变量：

1
min_price

表示到当前为止，前面出现过的最低价格。

然后每天都试一试：

1
prices[i] - min_price

看看如果今天卖出，利润能不能刷新最大值。

1
class Solution(object):
2
    def maxProfit(self, prices):
3
        """
4
        :type prices: List[int]
5
        :rtype: int
6
        """
7
        if len(prices) == 0:
8
            return 0
9

10
        ans = 0
11
        min_price = prices[0]
12

13
        for i in range(1, len(prices)):
14
            ans = max(ans, prices[i] - min_price)
15
            min_price = min(min_price, prices[i])
16

17
        return ans

为什么这样做是对的#

因为当我们遍历到第 i 天时：

• 如果今天卖出
• 那买入日一定只能从前面那些天里选
• 而前面那堆天数中，最优买点肯定就是最低价那天

也就是说，对于每个 prices[i]，最优利润就是：

1
prices[i] - 前缀最小值

所以我们只要一边更新前缀最小值，一边更新答案，就能在线性时间内解决问题。

这两行代码为什么顺序不能乱#

代码里的关键就是这两句：

1
ans = max(ans, prices[i] - min_price)
2
min_price = min(min_price, prices[i])

这里先更新利润，再更新最低价，逻辑上更清楚。

意思是：

1. 先把今天当成卖出日，用前面历史最低价来计算利润
2. 再看今天的价格能不能成为新的最低买入价

这样就天然保证了：

买入一定发生在卖出之前。

这个顺序很顺，读起来也不会拧巴。

结合样例走一遍#

比如：

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

初始化：

1
min_price = 7
2
ans = 0

1
ans = max(0, 1 - 7) = 0
2
min_price = min(7, 1) = 1

1
ans = max(0, 5 - 1) = 4
2
min_price = 1

1
ans = max(4, 3 - 1) = 4
2
min_price = 1

1
ans = max(4, 6 - 1) = 5
2
min_price = 1

1
ans = max(5, 4 - 1) = 5
2
min_price = 1

1
5

为什么最差答案是 0#

如果价格一路下跌，比如：

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

那不管怎么买卖，利润都不会是正数。

这时候最好的策略其实是：

不交易。

所以答案初始化为：

1
ans = 0

这样就能自然处理“全程亏本”的情况。

复杂度分析#

1
O(n)

1
O(1)

这题的本质#

虽然题目套了股票外壳，但它本质上做的是：

在遍历数组时，动态维护前缀最小值，并用它更新当前位置的最优答案。

你也可以把它理解成：

• 前面负责提供最便宜的买点
• 当前负责尝试今天卖掉能赚多少

所以它更像一道“前缀最值 + 贪心”的题，而不是股票模拟题。

和 122 题别混了#

这题是 LeetCode 121，只允许：

交易一次

所以目标是找一组最优的买入日和卖出日。

但如果是 LeetCode 122《买卖股票的最佳时机 II》，那就允许多次交易，思路会完全不一样。

一句话区分：

• 121：只做一笔，找最大单次利润
• 122：能反复做，把所有上涨段都吃掉

别把这兄弟俩炖成一锅股票乱炖。

小结#

这题最重要的不是股票，而是这个贪心思想：

1. 记录前面出现过的最低价格
2. 用当前价格尝试更新利润
3. 全程只扫一遍数组

如果只记一句话，我建议记这个：

前面找最低，当前算收益。

最低价稳住了，最大利润就能顺着遍历自己浮出来。 题目不难，但很适合拿来练“前缀最值 + 贪心”这种基础而高频的思路。🦐