LeetCode 122 题“买卖股票的最佳时机 II”算是我刷题过程中印象比较深的一道题原因是它短小精悍解法短到让人怀疑自己是不是在做一道 Easy 题但背后的思路延展性极强。从这道题出发可以一路串起整个股票交易系列的动态规划体系所以它经常被面试官拿来当“引子”先写贪心再问动态规划再追问带手续费、带冷冻期怎么办。这篇文章想把这道题讲透包括题目本质、贪心为什么合法、动态规划怎么推、两种思路怎么选、和系列其他题目的关系以及我自己刷题和面试中踩过的坑。无论你是刚开始刷 LeetCode 的新手还是准备校招社招想突击股票系列的选手这篇应该都能给你一些直接能用的东西。1. 题目到底在说什么先别急着写代码1.1 从“最佳时机 I”到“最佳时机 II”的变化在哪里如果你先刷过第 121 题“买卖股票的最佳时机”再看这道题第一反应往往是这不就是把一次买卖改成多次买卖吗对但“改成多次买卖”这几个字直接改变了整个问题的求解思路。第 121 题的约束是“最多只能完成一笔交易”所以你只需要找到一个买入点和一个卖出点让卖出价减买入价最大。这个问题用“记录历史最低价 更新最大利润”一趟扫完本质上是一个动态规划退化后的写法。但第 122 题允许你多次买入卖出而且每天最多只能持有一股这就意味着你不能简单地把“差价最大的那一段”拿出来而是要思考如何把一整段价格走势拆成若干段上升区间把每一段都吃到。这道题的输入很简单一个数组pricesprices[i]表示第i天的价格。输出是一个整数表示在满足约束条件下能拿到的最大利润。约束条件就两条任意时刻最多持有 1 股可以多次买卖但必须在再次买入前卖出。提示这里的“再次买入前卖出”很关键它杜绝了你一边持有股票一边继续买入的可能也决定了贪心算法在这里是安全的。1.2 把交易拆成相邻两天的差价我第一次做这道题的时候第一反应是找“局部最低点”和“局部最高点”然后循环做差累加。这当然能解出来但代码写起来要处理一堆边界什么算局部低点、数组最后一天是高点还是低点、要不要单独处理只有一个元素的情况。后来看到一个更简洁的视角把每一天和前一天的价格差算出来diff prices[i] - prices[i-1]。如果diff 0就把这个差值加入利润。这样想的话问题就变成了一个特别直观的模型只要今天的价格比昨天高这就代表了一段“可以赚到的上升段”把所有上升段加起来就是最大利润。为什么可以这么做因为一次持有多日的交易本质上可以拆成若干个相邻差值的累加。比如你第 1 天买、第 4 天卖利润等于(prices[3]-prices[0])它等价于(prices[1]-prices[0]) (prices[2]-prices[1]) (prices[3]-prices[2])。也就是说总利润就是每天相邻差的总和。而你为了最大化总利润自然会想把所有正的相邻差都吃掉负的相邻差全部避开。这样整个问题就从“选择买卖时机”变成了“选择哪些涨价的相邻段参与利润”。用更生活化的例子来理解你在市场里卖一件商品价格每天波动。只要今天批发价比昨天高你手里有货的话今天就一定该以更高的价格卖出哪怕明天价格还会更高你也可以今天先卖明天再用同样的价格买回来继续持有。关键在于当价格持续上涨时连续套利的效果等同于一直持有到最后一天再卖。这就是贪心合法性的直观来源。2. 贪心解法的完整推演2.1 为什么累加所有正差价就是最优解可能很多人会问一个问题如果我今天 5 块买入、明天涨到 6 块我卖了赚 1 块后天涨到 7 块按理说不卖能赚 2 块卖了再买不就是只赚了 1 块加 1 块不还是 2 块吗对数值上完全一样。这正是贪心能成立的原因之一在连续上涨的行情里“每天卖出再买入”的总利润等于“一直持有到最后”的利润两者算出来的结果相同。再换个角度想假设有一个最优的买点p和卖点qp q这段交易的利润是prices[q] - prices[p]它等于p到q之间所有相邻天差的总和。如果其中某一段相邻差是负数说明这中间存在价格回调那你完全可以把这一整段交易拆成两段避开那个负差利润只会更多不会更少。因此任何包含负差值区间段的交易方案都不可能是最优的。最优方案一定只包含所有正的相邻差。这就是从“反证”角度理解贪心的核心局部最优的“吃下每个正涨幅”最终拼接起来就是全局最优。注意这不是所有贪心题都成立的。普通的找零钱问题里贪心不一定正确但股票这道题之所以成立是因为它没有“买卖次数限制”也没有“连续交易限制”利润可以无限拆分累加所以贪心没有后效性你今天做不做这笔交易不会影响后面交易的选择。2.2 实现代码与每一行在做什么贪心的代码几乎是最短的一档但每一行都有它的原因。先看 Python 版本from typing import List class Solution: def maxProfit(self, prices: List[int]) - int: profit 0 for i in range(1, len(prices)): diff prices[i] - prices[i - 1] if diff 0: profit diff return profit这里从i 1开始遍历因为第 0 天没有前一天。每次计算今天和昨天的差价diff如果为正就累加否则跳过。这里没有真正的“买入”“卖出”操作只是数值上把利润累加出来但它等价于在每个局部低点买入、局部高点卖出的完整过程。再看 Java 版本class Solution { public int maxProfit(int[] prices) { int profit 0; for (int i 1; i prices.length; i) { if (prices[i] prices[i - 1]) { profit prices[i] - prices[i - 1]; } } return profit; } }Java 和 Python 的逻辑一样只是语言语法不同。这里有一个很常见的疑问如果prices长度为 0 或者 1循环条件直接不满足返回 0正好是正确的答案因为一天之内无法完成买卖利润只能是 0。所以这个写法天然处理了边界情况不需要额外判断。我自己在面试中写这题时会在写完代码后补一句解释diff只取正数因为负差价代表下跌应该跳过累加的正差价总和等价于在每一段上涨前买入、上涨后卖出。这句话能让面试官立刻确认你是真的理解而不是背了模板。3. 动态规划解法一眼看到股票系列全貌3.1 状态定义和转移方程怎么来的面试官通常不会只满足于贪心尤其是当你表明自己刷过股票系列时更大概率会追问“你还能用什么方法解”这时候动态规划就要出场了。动态规划在这道题里不占代码优势甚至写起来比贪心长得多但它最大的价值是可扩展性——换一个题目约束贪心可能直接失效DP 框架却往往只是改一行状态转移。在股票系列里通用的 DP 状态定义是dp[i][0]表示第i天结束时手里不持有股票的最大现金利润dp[i][1]表示第i天结束时手里持有 1 股股票的最大现金利润。这里“现金利润”可以理解为把这些交易都完成后账户里相比初始状态多了多少钱。有了这两个状态转移方程就顺着“今天能做什么操作”自然推出来了如果今天结束时手里不持股那只能有两种情况昨天也不持股今天什么都不做所以状态是dp[i-1][0]昨天持股今天把股票卖掉了所以状态是dp[i-1][1] prices[i]。两者取最大即dp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i])。如果今天结束时手里持股同样有两种情况昨天就持股今天继续拿着不动所以状态是dp[i-1][1]昨天不持股今天买入股票花掉prices[i]的钱所以状态是dp[i-1][0] - prices[i]。两者取最大即dp[i][1] max(dp[i-1][1], dp[i-1][0] - prices[i])。这个转移方程里最值得注意的一点是买入时用dp[i-1][0] - prices[i]而不是0 - prices[i]因为买入花的钱要减去之前已经赚到的利润。如果之前已经赚了 100再花 5 块买入现金利润是 95如果忽略之前赚的钱直接写成-prices[i]就会把已经赚到的利润丢掉结果完全错误。3.2 初始化细节与空间优化初始化的核心是第 0 天的状态第 0 天不持股现金利润肯定是 0第 0 天持股说明花了prices[0]买入现金利润是-prices[0]。代码写出来是这样from typing import List class Solution: def maxProfit(self, prices: List[int]) - int: n len(prices) if n 2: return 0 dp [[0, 0] for _ in range(n)] dp[0][0] 0 dp[0][1] -prices[0] for i in range(1, n): dp[i][0] max(dp[i - 1][0], dp[i - 1][1] prices[i]) dp[i][1] max(dp[i - 1][1], dp[i - 1][0] - prices[i]) return dp[n - 1][0]最后返回dp[n-1][0]而不是dp[n-1][1]因为最后一天结束后手里不应该还持有着股票持有股票的现金利润反而不利于整体收益。当然你直接返回max(dp[n-1])在多数情况下也不会出错因为最优策略最后必然是把股票卖出但写dp[n-1][0]更符合逻辑语义。这个二维数组版本空间复杂度是 O(n)。但由于第i天的状态只依赖第i-1天完全可以用两个变量滚动更新把空间压到 O(1)from typing import List class Solution: def maxProfit(self, prices: List[int]) - int: n len(prices) if n 2: return 0 dp0 0 dp1 -prices[0] for i in range(1, n): new_dp0 max(dp0, dp1 prices[i]) new_dp1 max(dp1, dp0 - prices[i]) dp0, dp1 new_dp0, new_dp1 return dp0这里一定要用两个临时变量new_dp0和new_dp1接住新值再统一赋值。如果直接写dp0 max(dp0, dp1 prices[i])然后下一行用更新后的dp0去算dp1就会造成状态污染因为dp1的转移需要的是“计算前”的dp0而不是“计算后”的dp0。这是很多人第一次写滚动 DP 时最容易犯的错。4. 贪心和动态规划的取舍4.1 两种解法的核心差异对比对比维度贪心解法动态规划解法代码长度极短10 行以内稍长20 行左右时间复杂度O(n)O(n)空间复杂度O(1)O(1)滚动优化后理解难度直观但容易“不知道为什么对”需要接受状态定义但逻辑严谨扩展性低改一题约束就失效高改状态即可适配衍生题面试表达要求必须能证明贪心正确性只需把转移方程讲清楚从刷题策略来看如果只是为了 AC 这一题贪心肯定是最优选择。但如果你的目标是“把股票系列一网打尽”我建议至少要熟练手写动态规划的版本因为接下来要讲的第 309 题冷冻期、第 714 题手续费本质上都是在这个 DP 框架上做小改动而贪心版本在那些题目里往往不再适用或者要额外处理很多细节。4.2 面试官想听什么面试里如果被问到这道题我的建议是第一遍讲贪心重点讲清楚“为什么局部正差价累加等于全局最优”最好配合一两个例子比如[1, 5, 3, 6]手动算一下(5-1) (6-3) 7然后指出如果只买一次最大是6-15而多次交易能拿 7这就说明了“多次买卖”带来的增量。这里要注意面试官问这类题最看重的不是你背没背过代码而是你能不能解释清楚边界条件、为什么负差价要跳过、为什么不用考虑手续费。如果面试官进一步问“你还能怎么解”再引出动态规划。此时可以主动把状态转移图描述出来持股、不持股两个状态今天可以操作也可以不动然后写出转移方程。能主动说出“这个 DP 框架可以扩展到冷冻期和手续费”通常是一个不错的加分项因为它展示了你在刷题时做过归纳总结而不只是单向的题海战术。5. 股票系列全家桶从 121 到 7145.1 五大变形题的解法脉络这道题的最大价值在于它是整个“股票买卖系列”地图里的枢纽。我建议你在做完本题之后顺手把下面几道题连起来刷因为它们之间呈现出一条非常清晰的“加约束”主线题号题目额外约束解法变化121买卖股票的最佳时机最多交易 1 笔一次遍历记录历史最低点122买卖股票的最佳时机 II可以交易任意多笔贪心累加正差价 / DP123买卖股票的最佳时机 III最多交易 2 笔DP 增加“交易次数”维度188买卖股票的最佳时机 IV最多交易 k 笔DP 增加 k注意 k 过大的优化309最佳买卖股票时机含冷冻期卖出后第 2 天才能买入DP 增加“冷冻期”状态714买卖股票的最佳时机含手续费每笔交易收手续费DP 转移方程中扣除手续费以第 714 题为例它只是把买入或卖出时的利润扣掉一个feedp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i] - fee)其他完全不变。再比如第 309 题状态多了一个“冷冻期”你需要区分“当天卖出后不能立刻买入”于是把持股状态拆成“当天买入”和“之前就持有”两种情况。这时候你就能明白为什么我在第 122 题宁愿多花时间把 DP 框架讲透——因为它不是一道孤立题而是整个系列的底座。5.2 算法选择与场景映射从实际工程视角看这类“动态规划多阶段决策”的抽象场景能映射到很多业务问题。比如你维护一个商品库存每天价格和成本都在波动你可以决定补货还是清仓这跟“持股/不持股”的状态几乎一模一样再比如你在做量化交易回测中的“最优无限制交易策略”不考虑手续费和滑点时收益上限公式就是所有正收益段之和这和贪心行为也高度一致。虽然真实交易里有手续费、冲击成本、最小交易单位等约束但它们的核心建模方式都是从这种“状态 转移 约束”的框架生长出来的。所以当你刷完这道题不妨把它理解成一个“模型能力放大器”不只是学会了一个数组遍历技巧而是掌握了一种把业务规则编写成 DP 状态机的思维方式。下一个需求来的时候你不会想“我该怎么遍历”而是会想“这个业务有哪些状态状态之间怎么转移有哪些约束”。6. 常见问题与易错点实录6.1 四个高频错误我见过不止一个新手在这题上栽跟头而且往往栽得莫名其妙。排在第一的错误是“试图模拟真实的买卖过程”也就是每次都去找真正的低点和高点结果代码写得很长边界还一堆问题。这个错误的核心原因是没意识到“差值累加”这种代数视角可以把问题大幅简化。第二个高频错误是写了if prices[i] prices[i - 1]但累加时手滑写成了prices[i] - prices[i - 1]这没问题但有人会写成profit prices[i]直接取当前价格而不是差值错误很明显但在紧张状态下容易犯。建议在本地多跑几个用例比如[1, 2]预期 1[2, 1]预期 0[1, 2, 3, 4]预期 3一眼就能验证对不对。第三个错误和动态规划相关初始化dp[0][1]写成了 0。如果第 0 天持股的利润是 0就相当于免费拿到一股这在现实中是不可能的也会导致后面所有状态算出来虚高。记住一旦持股就要减去买入价格所以dp[0][1] -prices[0]。第四个错误是在滚动更新 DP 数组时没有使用临时变量导致第i天的状态覆盖了第i-1天的状态后面计算的时候用了错误的前一天数据。这个问题很隐蔽因为数组很大时未必跑出明显错误但在[1, 2, 3]这种用例上很容易暴露错误写法可能算出 4而正确答案是 2。6.2 关于“什么时候能贪心”的追问面试官偶尔会换个角度问这道题为什么可以用贪心而第 121 题不行这是一个很好的总结性问题。核心区别在于第 121 题要求只能交易一次你一但决定在某个低点买入再在某个高点卖出中间的多次正差价就不能都吃进肚里因为买入一次之后不能再买所以“局部最优拼接”不成立而第 122 题不限制交易次数每个正差价都可以单独拿一次互不干扰所以贪心成立。另一个容易混淆的追问是“如果允许同一天先卖后买会怎样”。实际上在这道题的规则下即使允许贪心结果也不变因为连续上涨时先卖再买等价于继续持有这在数学上已经验证过了。但面试官这么问时更多是想确认你是否理解“持有状态”和“现金状态”之间的切换而不是真的想改题。这类追问没有标准答案但只要你把状态机的思维方式表达出来——股票账户在任意时刻只可能处于“持股”或“空仓”两种状态买入卖出就是在两个状态间切换——基本就能让人信服。就我个人经验来说这道题是“短代码、深逻辑”的典型。它的贪心解法短到可以一行写完但如果你只是背下那一行下一次遇到带手续费的变体题还是会懵。我建议刷完这道题后主动做一个小练习把动态规划版本改成支持“每笔交易扣手续费”的版本再改成“卖出后需要冷冻一天”的版本。做过这两个小改动之后你才算真正把这题吃透。这种从基础题推导出系列题套路的做法比盲目刷五十道题更有用也是我认为刷题最有价值的部分。