买卖股票的最佳时机

问题拆解

给一串每天的股价，只允许买入一次、之后某天卖出一次，求最大利润；亏本就返回 0。

暴力做法是枚举所有“买入日 < 卖出日”的组合，取差价最大者，时间复杂度 O(n^2)。但这里有个约束能利用：卖出必须在买入之后。

于是我固定“卖出日”来想：如果决定在第 i 天卖，最赚的买入点一定是第 i 天之前的历史最低价。这样每一天卖出的最优利润是 prices[i] - 到今天为止的最低价，答案就是这些利润里的最大值。

一旦“卖出日”固定，买入点就不用再枚举——它必然是此前的最低价。

一次遍历维护最低价

我边走边维护两个量：到目前为止见过的最低价 min_price，以及到目前为止的最大利润 best。

def maxProfit(prices: list[int]) -> int:
    min_price = float("inf")
    best = 0

    for price in prices:
        best = max(best, price - min_price)
        min_price = min(min_price, price)

    return best

顺序有讲究：先用当前价减去“今天之前”的最低价来更新利润，再把今天的价格纳入最低价。这样保证卖出日永远晚于买入日。初始利润设为 0，天然处理了“全程下跌、无法盈利”的情况。

换个视角，这也是一道被压扁的动态规划：设 dp[i] 为“第 i 天必须卖出”的最大利润，则 dp[i] = max(dp[i-1], 0) + (prices[i] - prices[i-1]) 这类递推同样成立，而我们只关心其中的最大值，于是状态被压成了 min_price 和 best 两个变量。

复杂度

指标	复杂度	原因
时间	O(n)	数组只遍历一次
空间	O(1)	只保存最低价和最大利润

可以迁移的模式

• “在 j > i 的约束下最大化 a[j] - a[i]”，都能靠“遍历时维护历史最优”解决；
• 贪心与 DP 常是一体两面：能用一两个滚动变量概括状态时，DP 就退化成一次遍历；
• 更新顺序决定正确性，务必让“历史信息”先于“当前元素”参与计算。

看到“先买后卖”“先低后高”这类带时序约束的极值问题，先想想能不能一边走一边记住历史最优。