买卖股票的最佳时机 图解题解

这道题真正在问什么

题目给一个数组 prices，prices[i] 是第 i 天的股价，只允许完成一笔交易——买一次、卖一次，且卖出必须在买入之后。求能拿到的最大利润，如果怎么交易都亏，就返回 0。隐藏的约束有两条：第一，交易只有一笔，不能反复低买高卖；第二，时间有方向，「卖在买之后」这条顺序限制正是本题和「找数组最大值减最小值」的本质区别。

为什么不能用全局最高价减全局最低价

一个诱人的错误想法是：最大利润不就是数组里的最大值减最小值吗？反例很快能构造出来——如果最高价出现在最低价之前，比如价格先冲到 9 再跌到 1，那这笔「先卖后买」的交易根本不合法。差值必须带方向：只能拿某一天的价格，去减它之前（含当天）出现过的最低价。

另一个直觉做法是两层循环，枚举所有买入日和卖出日的组合，取差值最大的一对。它是对的，但 n 天要试大约 n²/2 对，时间复杂度 O(n²)，价格数组一长就慢得不可接受。

关键观察：固定卖出日，最优买入日是确定的

换个角度想：假如已经决定第 i 天卖出，那买入日该选哪天？答案是唯一的——第 0 到第 i 天里价格最低的那天，因为卖价固定时，买得越便宜赚得越多。这样问题就从「枚举所有买卖组合」坍缩成「对每个卖出日，查一下它之前的最低价」。

而「之前的最低价」这个量，恰好可以在从左到右扫描时顺手维护：走到第 i 天时，用当天价格去更新一个变量 min_price，它就始终等于前 i 天的最低价，也就是所谓的前缀最小值。原来内层循环要做的整段查找，被压缩成一次比较。

一次遍历的每一步为什么成立

算法保持两个不变量：min_price 永远是「到目前为止见过的最低价」，best 永远是「到目前为止能实现的最大利润」。每到新的一天，先用当天价更新 min_price，再计算「假设今天卖」的利润 p - min_price 去更新 best。因为 min_price 只由今天及之前的价格构成，用它算出的每笔利润都自动满足「先买后卖」，不需要额外检查顺序。

有人会担心：先更新 min_price 再算利润，万一今天恰好是新低，算出的利润不就是 0 吗？没关系——今天买今天卖利润本来就是 0，不会污染 best；而真正的收益要等之后某天价格高于这个新低时才兑现，届时自然会被更新进去。

复杂度怎么算，哪些边界会翻车

时间 O(n)：数组只扫一遍，每天做一次取最小、一次取最大，都是常数操作。空间 O(1)：全程只用 min_price 和 best 两个变量，不需要任何额外数组。

两个真会翻车的边界：一是价格一路下跌时，任何交易都亏，正确答案是 0 而不是负数——把 best 初始化为 0、亏了就当不交易，这条就自动满足；二是别把本题和 LeetCode 122 混淆，122 允许多次买卖、贪心吃下每段上涨即可，而本题只许一笔交易，找的是历史最低点之后的最大单段涨幅。

Python

def maxProfit(prices):
    min_price = float("inf")  # 历史最低买入价
    best = 0                  # 最大利润
    for p in prices:
        min_price = min(min_price, p)   # 更新最低买点
        best = max(best, p - min_price) # 今天卖的利润
    return best

C++

int maxProfit(vector<int>& prices){
    int minPrice = INT_MAX, best = 0;
    for(int p : prices){
        minPrice = min(minPrice, p);    // 历史最低买价
        best = max(best, p - minPrice); // 今天卖的利润
    }
    return best;
}

Java

public int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE, best = 0;
    for (int p : prices) {
        minPrice = Math.min(minPrice, p);    // 历史最低买价
        best = Math.max(best, p - minPrice); // 今天卖的利润
    }
    return best;
}