Best Time to Buy and Sell Stock 是 LeetCode 里非常经典的一道数组题，也是很多人接触“贪心思想”时最早会做的一题。
这道题本身不难，代码甚至可以短到几行，但它很适合用来训练一种非常重要的思维方式：
在遍历过程中，动态维护“当前最优状态”。
一次遍历，同时维护最低买入成本和最大利润。
题目介绍
给定一个数组 prices，其中 prices[i] 表示某支股票在第 i 天的价格。
你只能选择：
-
某一天买入股票
-
在未来的某一天卖出股票
并且：
-
只能买卖一次
-
必须先买后卖
-
如果无法获利，就返回
0
也就是说，这道题本质上是在问：
在所有合法的买入卖出方案中，最大利润是多少？
例如：
prices = [7,1,5,3,6,4]
最大利润是：
6 - 1 = 5
因为可以在价格为 1 的时候买入，在价格为 6 的时候卖出。
示例
示例 1
输入：
prices = [7,1,5,3,6,4]
输出：
5
解释：
-
第 2 天价格是
1，买入 -
第 5 天价格是
6，卖出 -
最大利润为
5
示例 2
输入：
prices = [7,6,4,3,1]
输出：
0
解释：
这组数据一直在跌，没有任何一次买入卖出可以赚钱，所以返回 0。
先想暴力解法
这道题最直接的想法其实很自然：
-
枚举每一天作为买入点
-
再枚举后面的某一天作为卖出点
-
计算利润
-
取最大值
也就是检查所有：
prices[j] - prices[i] (j > i)
这种写法当然能做出来，但时间复杂度是：
O(n^2)
因为每个买入点都要去看后面所有卖出点。
当数组很大时，这样做效率就不够好了。
所以这道题真正要解决的问题是：
能不能只遍历一遍，就把答案求出来？
答案是可以。
这道题真正的关键
题目要求最大利润，而利润的公式是：
卖出价 - 买入价
如果我们从左到右遍历数组，假设当前来到某一天，价格是 price，并且把这一天当成“卖出日”去思考，那么我们要做的事情其实只有一件：
找到在它之前出现过的最低价格。
因为：
-
卖出价已经固定为当前价格
-
想让利润最大，就要让买入价尽可能小
所以对于当前这一天来说，最好的利润就是：
当前价格 - 之前出现过的最小价格
于是问题就变成了：
-
遍历到当前位置时，记录“历史最低价格”
-
用当前价格减去这个最低价格，得到当前可能利润
-
再用这个利润去更新全局最大利润
一遍扫描就够了。
这就是这道题的核心思想。
Java 代码
class Solution {
public int maxProfit(int[] prices) {
int cost = Integer.MAX_VALUE, profit = 0;
for (int price : prices) {
cost = Math.min(cost, price);
profit = Math.max(profit, price - cost);
}
return profit;
}
}
这段代码很短，但思路非常完整。
代码拆解
下面我们一行一行来看。
1. cost 和 profit 分别表示什么？
int cost = Integer.MAX_VALUE, profit = 0;
这里定义了两个变量：
-
cost：到目前为止，股票出现过的最低价格，也就是最低买入成本 -
profit：到目前为止，能够获得的最大利润
为什么 cost 初始值要设成 Integer.MAX_VALUE？
因为这样在第一次比较时：
cost = Math.min(cost, price);
无论第一个价格是多少，都会被更新成真实的股票价格。
而 profit 初始值设成 0，也很好理解：
因为题目说了，如果不能赚钱，就返回 0，所以利润最小就是 0，不可能是负数。
2. 为什么只需要一次遍历？
for (int price : prices) {
这句表示从左到右扫描整个价格数组。
关键在于： 每走到一天，我们只关心两件事：
-
之前最便宜的价格是多少
-
如果今天卖出，利润能有多少
这两个信息都可以在遍历过程中不断维护，因此不需要双重循环。
3. 为什么先更新 cost？
cost = Math.min(cost, price);
这句代码的作用是：
把当前为止出现的最低价格记录下来。
比如价格序列是：
[7,1,5,3,6,4]
遍历过程中的 cost 变化是：
-
第一天：
7 -
第二天：
1 -
后面一直保持
1
也就是说，cost 始终代表：
在当前这一天及之前，最低的买入价格是多少。
这一步是整道题的关键，因为后面的利润计算都依赖它。
4. 为什么利润写成 price - cost？
profit = Math.max(profit, price - cost);
因为当前遍历到的 price，我们可以把它理解成：
今天如果卖出，能赚多少钱？
而能赚多少，取决于之前最低的买入价 cost。
所以当前这一天的利润就是：
当前卖出价 - 历史最低买入价
然后再把这个利润和之前记录的最大利润比较，留下更大的那个。
于是 profit 始终表示：
截至当前这一天，最多能赚多少钱。
为什么这样写不会出错？
很多人第一次看到这段代码时，会有一个疑问：
先更新了
cost，再计算price - cost，会不会出现“当天买入当天卖出”的问题？
答案是：不会影响正确性。
因为如果当前价格正好刷新了最低价，那么：
price - cost = 0
也就是“今天买今天卖，不赚钱”。
这不会让答案出错，因为真正有意义的利润，一定会在未来某一天价格更高时体现出来。
而且题目要求的是最大利润，保留 0 也符合题意。
手动模拟一遍
我们用题目的经典例子来完整走一遍：
prices = [7,1,5,3,6,4]
初始状态：
cost = ∞
profit = 0
第一天，价格 7
更新最低成本：
cost = min(∞, 7) = 7
更新利润：
profit = max(0, 7 - 7) = 0
当前状态：
cost = 7
profit = 0
第二天，价格 1
更新最低成本：
cost = min(7, 1) = 1
更新利润：
profit = max(0, 1 - 1) = 0
当前状态：
cost = 1
profit = 0
第三天，价格 5
更新最低成本：
cost = min(1, 5) = 1
更新利润：
profit = max(0, 5 - 1) = 4
当前状态：
cost = 1
profit = 4
第四天，价格 3
更新最低成本：
cost = min(1, 3) = 1
更新利润：
profit = max(4, 3 - 1) = 4
当前状态：
cost = 1
profit = 4
第五天，价格 6
更新最低成本：
cost = min(1, 6) = 1
更新利润：
profit = max(4, 6 - 1) = 5
当前状态：
cost = 1
profit = 5
第六天，价格 4
更新最低成本：
cost = min(1, 4) = 1
更新利润：
profit = max(5, 4 - 1) = 5
最终答案：
5
也就是在价格 1 时买入，在价格 6 时卖出。
再看一组无法获利的情况
例如：
prices = [7,6,4,3,1]
遍历过程中：
-
cost会不断变小 -
但是
price - cost始终不会大于0
所以最终：
profit = 0
这正好符合题意。
这道题本质上是在考什么？
这题表面上是股票题，但它真正考的并不是金融知识，而是数组中的“动态最优维护”。
第一，是否能把问题转换成局部信息维护
很多人一开始只会想着：
-
买在哪一天
-
卖在哪一天
-
要把所有组合都试出来
但这题真正高效的做法是发现：
对于每一天作为卖出点来说，我只需要知道它前面最小的价格。
一旦想到这一点，双重循环就可以压缩成单次遍历。
第二，是否理解“遍历时顺手维护答案”
这道题非常典型地体现了一个技巧：
在扫描数组时，不断维护某个历史最优值。
这里维护的是：
-
历史最低价格
-
历史最大利润
以后你会在很多题里看到类似套路，比如：
-
最大子数组和
-
最高海拔
-
最小前缀值 / 最大前缀值
-
动态维护区间最优答案
第三，是否区分“状态”和“答案”
这题里：
-
cost是状态，表示当前为止最低买入成本 -
profit是答案，表示当前为止最大利润
把这两个变量分清楚，代码自然就会非常清晰。
复杂度分析
假设数组长度为 n。
时间复杂度
整段代码只遍历了一次数组，每个元素只处理一次，所以时间复杂度是：
O(n)
空间复杂度
只用了两个额外变量：
-
cost -
profit
所以空间复杂度是：
O(1)
这也是这道题最优的做法。
和动态规划有什么关系？
很多人刷到这题时，会听别人说这是“动态规划”，也有人说这是“贪心”。
其实这道题从不同角度都能解释。
从贪心角度看
我们始终贪心地维护：
到当前位置为止最便宜的买入价格。
这样一旦当前价格适合卖出，就能立刻得到当前位置的最优利润。
从动态规划角度看
也可以把它理解成：
-
cost是前缀最小值 -
profit是前缀最大利润
每一步都由前一步状态转移而来。
不过在实际面试或者写题解时，这题通常更常被归类为：
一次遍历 + 贪心维护最小值。
因为这种解释最直观，也最容易理解。
为什么这题很经典？
因为它短，但非常有代表性。
它代表了一类常见问题：
在遍历过程中，如何利用“历史信息”快速得到当前位置的最优答案？
本题中：
-
历史信息是“之前最低价格”
-
当前决策是“如果今天卖出，利润是多少”
把历史信息维护好，当前位置的答案就能立刻算出来。
这其实是一种非常常见的算法思想。
总结
这道题的核心可以概括成一句话：
从左到右遍历数组，始终维护历史最低买入价，并用当前价格减去它，来更新最大利润。
具体步骤就是：
-
用
cost记录遍历过程中出现过的最低价格 -
把当前价格当作卖出价
-
计算当前可能利润
price - cost -
用
profit维护全局最大利润 -
遍历结束后返回结果
这道题非常适合作为“数组遍历维护最优解”的入门题。 如果你能真正理解它，后面再去看：
-
买卖股票的最佳时机 II
-
买卖股票的最佳时机 III
-
买卖股票的最佳时机含冷冻期
-
买卖股票的最佳时机含手续费
你会更容易意识到：
股票问题的本质，往往不是模拟买卖过程，而是设计状态并维护最优转移。
