LC121　买卖股票的最佳时机¶

简单通过率 60.2%python3核心代码模式贪心算法样例通过牛客 AC数组动态规划

讲解章节：线性 DP

一句话

一趟扫描，边走边记历史最低价，用当天价格减它更新答案。

解题思路¶

这题考什么¶

朴素想法是枚举买入日 i 与卖出日 j（i < j）取 prices[j] - prices[i] 的最大值，这是 O(n^2) 对。把它换个枚举顺序就塌成线性：

**固定卖出日 j，最好的买入日一定是 j 之前的最低价那天。**

这句话不需要证明技巧，它就是定义——卖出价定死为 prices[j] 时，利润 prices[j] - prices[i] 只随 prices[i] 变小而变大，而 i 可以在 [0, j-1] 里随便挑，当然挑最小的。于是

答案 = max over j of (prices[j] - min(prices[0..j-1]))

括号里那个 min 是一个前缀最小值，从左往右扫的时候顺手就能维护，不需要重算。这样每个 j 只花 O(1)，总共 O(n)。

代码里把「更新最低价」和「更新答案」写在同一趟里，靠的是顺序：对第 j 天，先拿它和已有的最低价比——若它更低，它只能当未来的买入日，今天卖不出正收益（自己减自己是 0，而答案下界本来就是 0）；若它不更低，说明当前最低价来自更早的某天，i < j 的先后约束自动满足，可以放心结算 prices[j] - min_price。这条「买在卖之前」的约束完全由扫描顺序保证，代码里没有任何显式的下标比较。

换个视角，这题也是最大子数组和（见 LC53）：对相邻价差数组 d[k] = prices[k] - prices[k-1] 求最大连续子段和，因为一段连续价差之和正好是首尾两天的差价。两种视角算出的是同一个量，本题解取前缀最小值的写法更直白，也少建一个数组。

数据规模与复杂度¶

1 <= prices.length <= 1e5，0 <= prices[i] <= 1e4。时间 O(n)：一趟扫描；空间 O(1)：两个整数。 O(n^2) 的双重枚举在 n = 1e5 时是 5e9 次比较，Python 下完全跑不完。

坑在哪¶

只允许买卖各一次，且必须先买后卖。所以答案不是「所有上涨段之和」—— 那是 LC122 允许多次交易时的答案。[1,5,1,5] 本题答案是 4 而不是 8。
答案下界是 0，不是负数。价格一路下跌时不交易即可，所以 best 初值取 0，且只在差价为正时才更新。初值取负无穷会在 [7,6,4,3,1] 上返回 -1，与样例 2 期望的 0 不符。
min_price 初值取 prices[0]，靠的是题面保证数组非空（长度下界是 1）。取 0 是错的：题面允许价格为 0，但更要紧的是「历史最低价」这个量必须来自真实存在的某一天，凭空取 0 会让第一天就结算出虚假利润。
更新最低价与更新答案写成 if / elif 是有意的，不是省事。进 if 分支说明今天创了新低，今天卖只能得 0，而 best 本来就不小于 0，跳过结算不会漏解；分开写成两个独立的 if 也对，只是多做一次减法。
单日数组（n == 1）答案是 0：唯一的那天既买又卖不被允许，本题解自然得到 0——循环只跑一轮，那一轮里 price 与 min_price 相等，两个分支都不改动 best。
返回的是最大利润这个数，不是买卖的日期。判题严格比对。

样例复核¶

prices = [7,1,5,3,6,4]，min_price 初值 7、best 初值 0：

7 -> 不低于 7？相等不进 if，7-7=0 不大于 best，best 仍 0
1 -> 创新低，min_price = 1
5 -> 5-1 = 4 > 0，best = 4
3 -> 3-1 = 2 不大于 4，best 仍 4
6 -> 6-1 = 5 > 4，best = 5
4 -> 4-1 = 3 不大于 5，best 仍 5
返回 5，与样例一致（第 2 天买、第 5 天卖）。

prices = [7,6,4,3,1]：每一天都创新低，结算分支一次都没进，返回 0，与样例一致。

参考实现¶

solutions/leetcode/LC121/sol.py
from typing import List, Optional


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 历史最低价，也就是「到今天为止最好的买入价」。初值取第一天的价格
        # （题面保证数组非空）；取 0 会凭空造出一个不存在的买入日
        min_price = prices[0]
        # 答案下界是 0：一路下跌就干脆不交易。初值取负无穷会让全程下跌的数据返回负数
        best = 0
        for price in prices:
            if price < min_price:
                # 今天创了新低，它只能当**未来**的买入日。今天卖出等于自己减自己，
                # 收益 0，不可能超过已有的 best，所以这一支不必再结算
                min_price = price
            elif price - min_price > best:
                # 今天没创新低，说明 min_price 来自更早的某一天，
                # 「买在卖之前」的约束由扫描顺序自动保证，可以放心结算
                best = price - min_price
        return best

LC121 买卖股票的最佳时机¶