当前位置：首页 > ops >正文

[从零开始面试算法] (12/100) LeetCode 121. 买卖股票：一次遍历的“后悔药”

ops 2025/9/7 16:33:06

引言

欢迎来到本系列的第十二篇！今天，我们将首次涉足一个非常庞大且经典的面试题系列——股票买卖问题。我们将从这个系列中最简单、最基础的一道题 LeetCode 121. 买卖股票的最佳时机 开始。

这道题表面上看似简单，但它背后蕴含的贪心思想或动态规划的思维方式，是解决更复杂股票问题的基石。

很多同学（包括我！）在初次接触这道题时，可能会陷入一种复杂的思维模式：“我是不是要先找到一个最低点，然后再找它后面的最高点？如果后面有更低的最低点怎么办？” 这种思路虽然符合直觉，但实现起来却容易变得复杂。

本文将带你一起：

分析这种“寻找极值点”的直觉思路。
提炼并掌握一个极其简洁的一次遍历解法，我称之为“后悔药”模型。
通过代码，深刻理解如何通过维护“历史最低价”来动态求解“最大利润”。

一、题目呈现

题目编号：121. 买卖股票的最佳时机
题目难度：简单
题目链接：121. 买卖股票的最佳时机 - 力扣 (LeetCode)
题目描述：

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

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

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，则返回 0 。
示例：
- 输入: [7,1,5,3,6,4] -> 输出: 5 (解释: 在第 2 天（价格 = 1）买入，在第 5 天（价格 = 6）卖出，最大利润 = 6-1 = 5。)
- 输入: [7,6,4,3,1] -> 输出: 0 (解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。)

二、我的思考：复杂的“寻找极值点”思路

（这里完全采用你的笔记思路）

看到题目要求“最大利润”，也就是价格差最大，我的第一反应是：

先遍历数组，找到一个价格最低点（“极小值”），把它当作我的买入点。

然后，在这个买入点之后，再遍历一遍，找到一个价格最高点，计算利润。

但这里有一个问题：如果在这个最低点后面，又出现了一个更低的最低点呢？那我的最佳买入时机就可能改变了。

所以，我的思路变得更复杂了：我需要不断地寻找局部最低点，然后计算从这个最低点出发能获得的最大利润。最后，在所有这些“局部最大利润”中，再找到那个全局最大的。

这个思路是正确的，它比 O(n²) 的纯暴力（遍历所有买入卖出组合）要高效。但它的逻辑分支很多，需要处理各种“分段”和“比较”，代码实现起来容易出错且不够简洁。

那么，有没有一种更简单、更统一的思维模型呢？

三、豁然开朗：一次遍历的“后悔药”模型

让我们换一个角度思考。我们不需要瞻前顾后，只需要遍历一次，在每一天都做出“当下”的最优决策。

想象一下，你正坐着时光机，一天一天地穿越价格历史。在每一天 i，你都可以问自己一个问题：

“如果我必须在今天（第 i 天）卖出股票，那么我能获得的最大利润是多少？”

答案很显然：要想今天卖出赚得最多，我当初的买入价必须是在今天（第 i 天）之前的所有日子里，价格最低的那一天。

这个思想给了我们一剂“后悔药”：我永远可以假定自己是在历史最低点买入的。

算法流程诞生了：

我们只需要维护两个变量：
- min_price：记录到今天为止，我所见过的历史最低价。
- max_profit：记录到今天为止，我所能获得的最高利润。
我们从第一天开始遍历到最后一天。在每一天 price：
- 第一步：计算潜在利润。我用今天的价格 price 减去我之前记录的 min_price，看看如果今天卖出能赚多少。然后，我用这个“潜在利润”去更新我的 max_profit，取两者中较大的那个。
- 第二步：更新“后悔药”。我再看看今天的价格 price 是不是比我之前记录的 min_price 还要低。如果是，我就更新 min_price。这样，我就为未来的日子准备好了新的“历史最低买入价”。
遍历结束后，max_profit 里存储的就是全局的最大利润。

四、C++ 最优代码与详解

这个“一次遍历”的思路，可以被翻译成极其简洁的代码。

完整代码

#include <vector>
#include <algorithm> // 为了使用 std::min 和 std::max
#include <climits>   // 为了使用 INT_MAXclass Solution {
public:int maxProfit(std::vector<int>& prices) {// 1.int min_price = INT_MAX;int max_profit = 0;// 2.for (int price : prices) {// 3.max_profit = std::max(max_profit, price - min_price);// 4.min_price = std::min(min_price, price);}// 5.return max_profit;}
};

代码逐点解释

int min_price = INT_MAX; int max_profit = 0;
初始化历史最低价为一个不可能达到的最大值，确保第一个价格能成为初始的最低价。初始化最大利润为 0，因为题目规定如果无利润则返回 0。
for (int price : prices)
遍历每一天的价格 price。
max_profit = std::max(max_profit, price - min_price);
更新最大利润。计算“今天卖出的潜在利润”（price - min_price），并和之前记录的 max_profit 比较，取更大的那个。注意：在第一次循环时，min_price是INT_MAX，所以 price - min_price 是一个负数，max_profit 仍然是 0，这是正确的。
min_price = std::min(min_price, price);
更新“后悔药”。在今天的价格 price 和之前的 min_price 之间，选择更小的那个作为新的历史最低价，为明天的决策做准备。
return max_profit;
遍历结束后，max_profit 就是全局的最大利润。

重要细节：为什么是先更新 max_profit 再更新 min_price？因为题目要求必须在未来的某一天卖出。如果在同一天买入和卖出，利润为 0。我们的代码顺序保证了，在计算当天利润时，使用的 min_price 一定是当天或当天之前的最低价，完美地符合了“先买后卖”的规则。

五、总结与收获

复杂度分析：我们只对价格数组进行了一次遍历，因此时间复杂度为 O(n)。我们只使用了两个额外的变量，空间复杂度为 O(1)。这已经是这道题的最优解。
核心思想：这道题是贪心算法或动态规划的一个极简应用。其核心在于，我们不需要考虑所有复杂的买卖组合，只需要在遍历过程中，动态地维护“到目前为止的最低价格”和“到目前为止的最大利润”这两个状态即可。
关键技巧：“先计算当天可能的最大利润，再更新当天的价格为可能的历史最低价”这个顺序，巧妙地处理了“先买后卖”的时间限制。