BM80　买卖股票的最好时机(一)¶

简单通过率 52.8%python3核心代码模式样例通过牛客 AC贪心动态规划

牛客原题　源码

讲解章节：线性 DP

一句话

边扫边记历史最低价，用今天的价格减它更新最大差值。

解题思路¶

这题考什么¶

只做一笔交易时，收益就是「卖出价减去之前某天的买入价」，所以对每个卖出日 i，最优买入价必然是 prices[0..i-1] 里的最小值。一趟扫描同时维护「历史最低价」与「已知最大收益」两件事即可，无需回头。

写成 DP 是同一回事，两个状态：

hold[i]  = 第 i 天结束时手上**有**股票的最大收益
empty[i] = 第 i 天结束时手上**没有**股票的最大收益

转移方程（只允许买一次，所以买入时从 0 起算而不是从 empty[i-1] 起算）：

hold[i]  = max(hold[i-1],  0 - prices[i])
empty[i] = max(empty[i-1], hold[i-1] + prices[i])

hold 是「负价格的最大值」，也就是历史最低价取反——两种写法在这里完全等价。答案是 empty[n-1]，即最大差值；empty 的初值 0 保证了「不交易」永远是可选项，所以无法获利时自然返回 0。这道题正是 BM81（不限次数）与 BM82（最多两笔）的基例，对比着看能看清「交易次数」这一维是怎么长出来的。

数据规模与复杂度¶

0 <= n <= 1e5，0 <= val <= 1e4，时限 2 秒（其他语言）。单趟扫描，时间 O(n)、空间 O(1)，与题面要求一致。收益上界 1e4，不涉及大整数。

坑在哪¶

历史最低价不能初始化成 0。题面允许价格为 0，但用 0 起手意味着「第 0 天之前就以 0 元买进过」，[8,9] 会被答成 9 而不是 1。代码用 None 表示「还没有任何可买入的日子」，第一天必定走进赋值分支。
买入必须严格在卖出之前。先更新最低价再算差值看似违反这一点，但当天更新最低价时 p - low 恰好为 0，不会虚增收益—— 代码里的 elif 正是利用这一点：p < low 的那天不可能同时是最优卖出日。
不能获利时返回 0 而不是负数，best 从 0 起手即可，无须额外判断。
n == 0 时循环不执行，直接返回 best = 0，与题面允许的空数组一致。
求的是一次买卖的最大差值，不是所有上涨段之和；把 BM81 的贪心累加套过来会在 [1,2,1,2] 上答成 2 而不是 1。

样例复核¶

[8,9,2,5,4,7,1]：low 依次 8 -> 2 -> 1，best 在 p = 9 时取 1、在 p = 7 时取 5，答案 5（第 3 天以 2 买入、第 6 天以 7 卖出），与期望输出一致。

参考实现¶

solutions/nowcoder/BM80/sol.py
from typing import List, Optional


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        best = 0                # 收益下界：一次都不交易也有 0，所以不会返回负数
        # 用 None 而不是 0 表示「还没有可买入的日子」：价格允许取到 0，
        # 拿 0 当初始最低价等于凭空多出一次 0 元买入
        low = None
        for p in prices:
            if low is None or p < low:
                low = p         # 刷新历史最低买入价
            elif p - low > best:
                # 走到这里说明 p >= low，今天当卖出日；p == low 时差值为 0，不影响答案
                best = p - low
        return best

BM80 买卖股票的最好时机(一)¶