标题里的“得”十有八九是手误正确写法应该是“买卖股票的最佳时期”。这道题我在各大在线题库都见过也是很多刷题清单上绕不开的一道经典。题目本身不难理解给一个数组第 i 个元素表示某只股票第 i 天的价格你只能选择某一天买入、之后的某一天卖出求最大利润如果怎么买卖都赚不到钱就返回 0。我第一次做的时候觉得这就是找个最大值减最小值结果连续两次提交都在“全局最大价出现在全局最小价之前”这种例子上翻车。后来花了一下午把它的几个变体全部刷完才意识到这道题背后其实藏着贪心、状态机 DP、二维 DP 一整条算法主线。这篇文章就按我当时的思考顺序来写适合正在刷题、准备技术面试或者想系统搞懂动态规划状态机的朋友。1. 先把这个经典问题读透什么才算“最佳时期”1.1 题目到底在问什么题目通常会这样描述给定一个数组prices其中prices[i]表示股票在第 i 天的价格。你只能在某一天买入并在之后的某一天卖出求能获得的最大利润。看两个标准示例输入[7,1,5,3,6,4]输出5。对应操作是第 2 天价格 1买入第 5 天价格 6卖出利润6 - 1 5。输入[7,6,4,3,1]输出0。价格一路下跌任何买入都会亏所以选择不交易利润为 0。这里有几个容易忽略的限定条件做题前必须先明确只能完成一笔交易也就是一次买入加一次卖出。买完再买、卖完再卖都不允许。卖出日必须在买入日之后严格大于不能同一天买同一天卖。可以不交易如果所有可能的买卖都是亏损答案是 0 而不是负数。很多人会下意识把它当成“数组最大值减最小值”这恰恰是最容易出错的地方。因为时间顺序是有约束的最大值可能出现在最小值之前那这笔“交易”在时间上根本不成立。比如[5, 1, 4]全局最大是 5全局最小是 1直接相减得到 4但 5 在第 1 天1 在第 2 天你不可能先以 5 买入再以 1 卖出。正确答案是第 2 天买、第 3 天卖利润 3。1.2 为什么这道题值得反复做作为一个刷题老手我可以说这道题是“性价比”极高的题目之一。代码量非常小最优解只有十几行但它考察的优化思维非常典型从暴力枚举到发现重复计算再到用单个变量维护中间结果。这个过程几乎是所有“双循环改单循环”类题目的标准范本。更关键的是它有一整个变体家族允许无限次交易只要卖完才能再买卖出后必须冷冻一天才能再买每次交易要扣手续费最多只能交易 k 次。每一个变体都对应一种典型解法从贪心到状态机 DP 再到二维 DP。也就是说认真吃透这一道题等于同时复习了算法面试里几个最重要的思想。这也是为什么很多刷题清单都会把它放在前几十题的位置上作为入门到进阶的衔接题。2. 从暴力枚举到一趟扫描最优解是怎么“长”出来的2.1 暴力解把每一对买卖都算一遍拿到题目最直接的想法就是枚举遍历每一个可能的买入日 i再遍历所有在它之后的日子 j计算prices[j] - prices[i]不断更新最大值。def max_profit_brutal(prices): n len(prices) best 0 for i in range(n): for j in range(i 1, n): profit prices[j] - prices[i] if profit best: best profit return best这段代码逻辑完全正确但时间复杂度是 O(n²)。刷题平台给的数据范围通常是 n 最大到 10 万量级O(n²) 意味着要做约 10^10 次运算直接超时。暴力解的意义只在于帮助我们确认问题语义真正要追求的是线性时间解法。2.2 关键观察每个卖出日的最优买入价就是历史最低价暴力解慢在哪里我们来看它的重复计算。对于固定的卖出日 j最优的买入日一定是在[0, j-1]区间内价格最低的那一天。也就是说对每个 j我们要知道的是min(prices[0..j-1])。但双重循环里内层循环对不同的 j 重复扫描了大量公共前缀这个最小值被反复重新计算。如果我们在从左到右遍历的过程中实时维护“到目前为止的最低价格”那么每个卖出日只需要一次减法就能得到最优利润。def max_profit(prices): min_price float(inf) best 0 for price in prices: if price min_price: min_price price elif price - min_price best: best price - min_price return best用[7,1,5,3,6,4]手动走一遍第 1 天价格 7最低价更新为 7利润 0第 2 天价格 1最低价更新为 1利润 0第 3 天价格 5利润 4best 变为 4第 4 天价格 3利润 2不更新第 5 天价格 6利润 5best 变为 5第 6 天价格 4利润 3不更新。最终得到 5。这个解法的本质是把“选买入日”的问题转化为“维护历史最低价”的问题让每个卖出日都能用 O(1) 时间算出最优买入结果。时间复杂度 O(n)空间复杂度 O(1)。2.3 动态规划的视角两个状态搞定如果觉得上面的思路太“技巧化”可以换一个更通用的状态机视角。我们把每天结束时的持仓状态分成两种hold手里持有股票当前收益是买入花掉的钱即某种意义上的“负收益”sold手里没有股票当前已经落袋的最大利润。因为整道题只允许一次买入所以买入只能发生在某一天且买入后的收益就是-prices[i]要么今天买入要么沿用之前某一个更便宜的买入点。写成转移式hold[i] max(hold[i-1], -prices[i])sold[i] max(sold[i-1], hold[i-1] prices[i])第一个式子其实就是在取“历史最低价的相反数”第二个式子就是在算“今天卖出能拿到的利润”。状态机跑完之后答案就是sold[n-1]。用代码写出来就是def max_profit_dp(prices): hold float(-inf) sold 0 for price in prices: sold max(sold, hold price) hold max(hold, -price) return sold这个版本和前面的单变量扫描本质上是同一个算法但状态机写法有一个巨大的好处后面遇到冷冻期、手续费这些变体时只需要在状态转移里加条件或加状态不需要重新发明思路。这也是为什么我建议把这两种写法都理解一遍。3. 边界条件与实现细节这些坑我替你们踩过了3.1 空数组和单元素数组如果数组长度小于 2根本不存在“买一天卖一天”的可能直接返回 0。很多新手在写min_price prices[0]初始化时会忘掉空数组的情况导致越界访问。稳妥的做法有两种要么先判空要么用float(inf)作为初始值。def max_profit(prices): if not prices: return 0 min_price prices[0] best 0 for price in prices[1:]: best max(best, price - min_price) min_price min(min_price, price) return best3.2 单调下跌时答案必须是 0[7,6,4,3,1]这种例子考察的是“不交易”的语义。如果你把best初始化为负数或者直接返回max(best, 0)之前没有处理负值结果就会出错。一个很简单的心法只要你不强制交易最差情况就是不赚不亏所以答案永远不会小于 0。初始化best 0本身就是对这个语义的保证。3.3 “买入日必须早于卖出日”的时间语义暴力解里我写的是j从i 1开始就是为了确保卖出日在买入日之后。有些人会用for j in range(n)然后加if j ! i的条件虽然也能跑但语义不清晰而且会把同一天买卖的情况也纳入计算。同一天买卖利润是 0不影响最终答案但这种写法容易在变体题里埋雷比如冷冻期版本里同一天买卖会绕过冷冻限制导致逻辑错误。养成j i 1的书写习惯更安全。3.4 变量初始化与溢出问题min_price float(inf)这种写法在 Python 里非常方便但在 C 或 Java 里对应的是INT_MAX然后用min函数更新。注意如果价格数组允许出现极大值比如到 10^9 量级利润prices[j] - prices[i]可能超过 32 位整数的表示范围这时候要用long long或 64 位整数。很多竞赛场景不会在这种基础题上卡溢出但养成“先看数据范围再定变量类型”的习惯对后面做难题很有帮助。4. 同源头变体题从“只做一笔”到“随便做几笔”4.1 无限次交易版把每个上升段都吃掉第一个变体是允许无限次交易但前提是卖完才能再买且同一时刻只能持有一股。这时有个很漂亮的贪心结论只要今天的价格比昨天高就认为昨天买入、今天卖出能赚差价把所有正差价加起来就是最大利润。def max_profit_multi(prices): profit 0 for i in range(1, len(prices)): if prices[i] prices[i - 1]: profit prices[i] - prices[i - 1] return profit为什么这样是对的比如[1, 3, 2, 4]两段上升分别是 1→3 和 2→4累加得到2 2 4等价于第一天买、第二天卖、第三天买、第四天卖。而如果第一段下跌 3→2 时强行持有反而会吃掉利润。把这个逻辑想明白后你会发现它和“差分数组取正数求和”是一回事。这个变体不建议用状态机 DP 去做虽然能做但绕远路贪心是最直接的。4.2 冷冻期版三状态状态机 DP第二个常见变体是卖出股票后第二天不能买入必须冷冻一天。这个限制一加之前的两个状态就不够用了。因为“今天能不能买”取决于“昨天是不是刚卖出”我们需要第三个状态来表达“处于冷冻期”或“刚卖完”的状态。三个状态定义如下hold今天结束时手里持有股票rest今天结束时处于冷冻期即今天刚卖出free今天结束时没有股票且不在冷冻期明天可以买入。转移关系hold可以保持不动也可以从free状态买入hold_new max(hold, free - prices[i])rest只能由hold卖出而来rest_new hold prices[i]free可以由rest冷却而来也可以由free继续保持free_new max(free, rest)代码实现def max_profit_cooldown(prices): hold float(-inf) rest 0 free 0 for price in prices: new_hold max(hold, free - price) new_rest hold price new_free max(free, rest) hold, rest, free new_hold, new_rest, new_free return max(rest, free)很多人在这个变体上翻车是因为只用了两个状态把冷冻期当成“暂停一天”处理结果状态转移写不对。记住一个原则状态机里一个状态对应一种“昨天结束时的局面”而不是“今天的动作”。想清楚昨天是什么状态、今天做什么动作、今天结束时进入什么状态转移方程就不会错。4.3 手续费版在状态转移里扣钱第三个变体是每次交易买入加卖出算一笔或者单次卖出要扣固定手续费。由于手续费只影响收益最简单的方式是在卖出时扣掉或者买入时扣掉二选一即可不要两头都扣。def max_profit_fee(prices, fee): hold float(-inf) sold 0 for price in prices: new_sold max(sold, hold price - fee) new_hold max(hold, sold - price) hold, sold new_hold, new_sold return sold这里有个小细节买入手时扣和卖出时扣的结果完全一样只是hold的初始化不同。如果你选择买入时扣那么hold的初始值应该是-prices[0] - fee选择卖出时扣就像上面的代码一样在卖出时减掉fee。做题时选一种写清楚注释即可。这个变体和无限次交易版对比很有意思没有手续费时贪心最优有手续费后贪心可能会因为频繁小额交易被手续费吃掉利润反而要用 DP 来权衡“要不要做这笔”。4.4 最多 k 次交易版二维 DP 与优化最后一个重量级变体是限制最多交易 k 次。这时贪心彻底失效冷冻期状态机也不够用需要一个二维状态dp[k][i]表示“最多进行 k 次交易在第 i 天结束时”的最大利润。转移式是dp[k][i] max(dp[k][i-1], prices[i] - prices[j] dp[k-1][j-1])其中第二项表示在第 j 天买入、第 i 天卖出加上之前最多 k-1 次交易的利润。直接枚举 j 是 O(kn²)但可以维护一个变量best_prev max(dp[k-1][j-1] - prices[j])在遍历过程中实时更新把复杂度压到 O(kn)。这个变体本身可以单独写一篇长文这里先给出思路框架把前面几个变体吃透后再来啃它会更顺手。4.5 变体对照表变体核心思路时间复杂度额外空间一次交易维护历史最低价O(n)O(1)无限次交易累加所有正向日差价O(n)O(1)冷冻期三状态状态机 DPO(n)O(1)手续费状态转移中加入费用项O(n)O(1)最多 k 次二维 DP 遍历优化O(kn)O(n)从这张表能看出一个规律限制越复杂状态越多但空间几乎都可以优化成常数。这就是状态机 DP 的威力也是这道题值得反复咀嚼的原因。5. 面试与实战中的经验别只背模板要能讲清“为什么”5.1 我刷这题时踩过的三个典型坑第一个坑是直接用全局最大最小相减。前面已经说过[5, 1, 4]这种例子一测就露馅。后来我把“时间顺序”四个字写在了笔记本首页做任何数组题都先问自己这个顺序约束能不能被打破第二个坑是在冷冻期版本里少写状态。我一开始天真地认为“休息一天”只需要在买入前判断昨天是否卖出于是只维护了两个状态结果在[1, 2, 3, 0, 2]这种例子上答案始终不对。后来把三状态的转移图画在纸上才意识到冷冻期会影响“买入资格”而这个资格本身就是一个独立状态。第三个坑是手续费版本里费用重复扣除。我试过买入时扣一次、卖出时又扣一次导致利润偏低调了半天才发现是自己把费用算了两次。这种低级错误在面试紧张时特别容易犯所以我现在写状态转移时一定会先写注释标明“费用在哪个动作发生时扣除”。5.2 拿到变体题后的判断顺序经过这一轮系统练习我总结出一个相对固定的判断流程先确认交易次数限制1 次、无限次、还是固定 k 次。再确认有没有附加条件冷冻期、手续费或者两者都有。然后选解法1 次用单变量扫描无限次且无手续费用贪心有附加条件用状态机 DPk 次用二维 DP。写代码前先在纸上把状态转移式列出来特别是状态机的“状态定义”要写清楚再动手。这个流程几乎可以套用所有买卖股票类变体题。我在模拟面试中试过只要第一步和第二步判断对了后面基本就是机械操作。5.3 讲给面试官的“答题路径”如果面试官让你现场做这道题我个人推荐这样讲先给暴力解明确说 O(n²)然后指出重复计算在哪里引出“历史最低价”这个核心优化紧接着补充一句“这个问题也可以用状态机 DP 来建模两个状态分别是持有和未持有”把转移式写出来。这样既展示了你对暴力到最优的推导能力又展示了你对更通用 DP 框架的掌握比直接甩最优解给面试官要好得多。如果面试官继续追问变体不要慌按上面的判断顺序走先加状态再改转移。状态机最怕的是“状态定义不清”所以开头那一句话特别重要“我用三个状态分别表示持有、冷冻期、可买入”。这句话一说出来面试官基本就知道你懂这题了。我自己后来在给别人做模拟面试时发现一个很灵验的判据能自己推导出“维护历史最低价”这个思路的候选人比直接背诵最优解的人在变体题上的表现要好一大截。因为前者理解的是“为什么要这样优化”后者记住的只是“答案长这样”。所以这篇内容的最后我还是想建议你别急着看最优解先自己把暴力解写出来然后盯着双重循环问自己一句——“这两层循环里哪些计算是重复的”想明白这个问题你就不只是会做这一道题而是掌握了一种通用的优化思维。