1. 这道题到底在说什么——读懂LeetCode122的真实意图1.1 题目已经不是简单模拟而是一个决策模型很多第一次刷到LeetCode122这道买卖股票的最佳时机 II的朋友第一反应都是这跟第121题有什么区别第121题是只能买卖一次求最大利润第122题变成了可以多次买卖但你手里始终只能持有一股必须在再次买入之前把手里那只卖掉。我先说一个很容易踩进去的误区有人以为多次买卖的意思是可以无限持股、反复横跳于是上来就写状态机模拟sell买入buy卖出循环里套条件判断最后利润算得七零八落。实际上这道题的本质不是模拟交易而是在一组价格序列上做一个决策优化——每一天你要决定是持有、买入还是卖出目标函数是最终手里现金增量最大化。只要你理解了这一层贪心策略的合理性就自然而然地浮出来了。题目给的输入price数组prices[i]代表第i天的股票价格。你可以在任意一天买入一股在之后的任意一天卖出一股不限交易次数但同一时间只能持有一股。求最大总利润。注意这里还有一个隐藏条件卖出和买入可以在同一天发生也就是当天卖掉、当天买回是被允许的这个细节在后面贪心证明里非常关键。1.2 最大利润的直觉先问自己敢不敢吃每一段差价我在面试实战里遇到一个很典型的场景候选人能很快背出只要后一天比前一天高就把差价加上但被问到为什么这样就是最大时往往只会说这就是贪心啊。这句话等于没说。让我先给直觉再给证明。假设股价序列是[1, 5, 3, 6, 8]。如果你全程只做一次交易最大利润是从最低点1买入、最高点8卖出拿到7。但如果允许多次交易最聪明的做法显然是把1买进5卖出赚4然后空仓等到3买进8卖出赚5总共9。你看把一次大波段拆成两个上升段利润反而更高。为什么因为中间那段下跌5到3你躲过去了相当于你不仅赚了上升的钱还规避了回撤的损失——这在单次交易里是做不到的。所以一个朴素的策略浮出水面只要第i1天的价格比第i天高我就在第i天买入、第i1天卖出赚这一段正差价如果下跌我就不交易空仓等着。把所有正差价累加起来就是总利润。这就是LeetCode122贪心策略的核心思想。问题只在于凭什么每一段正差价都吃不会互相冲突万一我今天刚卖出明天大涨我岂不是踏空别急下面我用数学方式把这个问题彻底讲透。2. 贪心策略的数学底气为何累加正差价等于最优解2.1 交易分解一笔长持等价于连续分段我需要先证明一个核心引理任意一段从第a天买入、第b天卖出的交易其利润等于这段区间内相邻两天所有正差价之和。这句话听起来有点反直觉我举个例子验证。假设你在第a天以价格P_a买入第b天以价格P_b卖出利润是P_b - P_a。我们把区间[a, b)里的相邻价格差拆开P_b - P_a (P_{a1} - P_a) (P_{a2} - P_{a1}) ... (P_b - P_{b-1})这个恒等式是精确成立的纯粹是代数恒等变形。现在关键来了如果中间某一段相邻差值是负数比如第k天到第k1天是下跌的那么这一段的贡献是负的。如果我们在第k天卖出、第k1天再买回来就可以把这个负贡献从总利润中剔除同时不改变其他段的收益。所以把一段长持有拆成若干小段只保留上涨段、过滤下跌段得到的利润一定不低于原始单笔交易的利润。更严格一点说任意交易策略产生的总利润都可以表示为某些区间上的首尾价差之和。把每个区间按上述恒等式展开成相邻差之和再重排累加你会发现总利润就等于每个上升相邻对prices[i1] prices[i]被选择次数 × prices[i1] - prices[i]的加权和。每种合法交易策略中任意相邻两天之间的买入-卖出对最多只能被利用一次吗这里需要小心同一天卖出再买入会让相邻对的选择次数叠加但每次选择同一相邻对最多只能贡献一次正向收益因为你的持有量始终只有一股。所以任何策略的总利润不可能超过所有相邻正差价的总和。这就是贪心最优性的核心证明骨架。贪心策略把所有正差价全部吃到正好到达这个上界所以它是最优的。2.2 贪心选择性质局部最优真的能推出全局最优很多人对贪心的印象是鼠目寸光、容易局部最优但全局翻车比如经典的硬币找零问题、0-1背包问题贪心都会失效。那为什么LeetCode122偏偏能贪关键在于这个问题具有两个性质贪心选择性质和最优子结构。贪心选择性质的意思是今天看到明天涨价今天买入明天卖出这一步一定包含在某个全局最优解里。为什么因为如果你在全局最优解中没有用这组相邻交易那你必然在某一天持有股票跨越了这段上升区间。反正这段差价你早晚要赚要么现在赚要么后面以包含在长持有期的形式赚。而前面证明了把长持有拆开、剔除下跌段只会让利润更高。于是现在吃掉这段差价不会让全局解变差。最优子结构就更简单了交易决策按天推进第i天之后的最优利润只取决于剩下的价格序列和第i天之前已经赚了多少现金无关。因为题目没有持仓数量限制以外的约束每一天的决策空间是独立的。这两个性质凑齐贪心就没有翻车的余地。注意这道题能贪心的隐含前提是交易次数无上限 没有手续费 没有冷却期 可以当天买卖。一旦这些条件被改动比如加一个买入手续费贪心就可能失效。这一点我在第5节专门展开。3. 从暴力到DP再到贪心三条路线如何收敛到最优3.1 暴力搜索/状态枚举的复杂度困境先看最简单的思路每天都有三种状态——空仓、持有、以及什么都不做其实可以并入当前状态。真正麻烦的是你无法确定今天是否应该买入因为未来是未知的。第一反应是回溯枚举所有可能的交易组合对每一天决定买入、卖出还是持有。这个决策树的深度是n天每个节点三个分支总路径数量指数级。哪怕用记忆化剪枝状态维度也包含当天是否持有以及当前累计利润并不好压缩。对n10^5级别的LeetCode输入这种方案直接超时。所以我建议你第一步别写搜索先把复杂度算清楚暴力指数、O(n^2)区间贪心枚举又太笨——其实O(n^2)的枚举法存在枚举每一对买入卖出日然后被重叠区间问题卡死。这条思路走不通原因是在多次交易约束下区间之间可以嵌套也可以串联单纯枚举区间对组合会爆炸。所以我们需要状态抽象也就是动态规划。3.2 动态规划的两个状态与转移方程动态规划是这类问题最稳的通解。定义两个状态dp[i][0]第i天结束时手里没有股票所持有的最大现金数。dp[i][1]第i天结束时手里正好持有一股所持有的最大现金数。注意这里现金数不是利润而是从开始到当前天累计下来的资产净值。初始条件dp[0][0] 0第一天开始手里没股票也持有0现金dp[0][1] -prices[0]第一天就买入花掉prices[0]。转移方程dp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i])意思是第i天空仓要么前一天也空仓今天啥也不干要么前一天持股今天卖出把卖出收入加进现金。dp[i][1] max(dp[i-1][1], dp[i-1][0] - prices[i])第i天持股要么前一天也持股今天不动要么前一天空仓今天买入现金减去买入成本。答案就是dp[n-1][0]因为最后一天手里留着股票没有意义必须空仓结算利润。这个DP的时间复杂度是O(n)空间复杂度O(n)。进一步观察可以发现dp[i][0]和dp[i][1]只依赖前一天的dp[i-1][0]和dp[i-1][1]所以可以用两个滚动变量来替代整个数组空间降到O(1)。我说句实在话如果你面试做到这道题先甩DP出来是完全没毛病的。DP不仅严密而且把状态空间讲得很清晰是面试官最容易验证你思路的路线。3.3 贪心是DP在特定条件下的简化形态现在把DP的推导拿过来和贪心对照。回到刚才这两个转移方程我们把式子变个形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])如果我们用贪心思维只要prices[i] prices[i-1]就认为应该赚这段差价。这句话翻译成DP的操作等价于在第i-1天卖出如果持有然后立即在第i天买回。卖出时现金增加prices[i] - prices[i-1]买回后状态重新变为持股。本质上贪心就是DP状态中每天都强制进行一次卖出再买入、只保留正向收益的路径。从数学角度看DP的max操作允许你自由选择交易时机而贪心直接把max拆成了对每个上涨步骤的累加。因为该问题无交易次数限制、无摩擦成本每个上涨段的收益是彼此独立的max整体可以分解为逐段max再加和。所以贪心是在DP更宽松条件下的解析解。我建议你把这个关系写在笔记里先秒杀DP再用DP解释贪心为什么成立。这比直接背一个三行贪心代码要有说服力得多。4. 代码落地实现细节、边界与复杂度验证4.1 核心实现你真的只需要三行LeetCode122的贪心实现极短我甚至见过有人用一行reduce写完。但我们写工程代码还是以可读性优先。我手写一版最标准的Python实现def maxProfit(prices: List[int]) - int: profit 0 for i in range(1, len(prices)): if prices[i] prices[i - 1]: profit prices[i] - prices[i - 1] return profit循环从第1天开始每次比较今天的价格和昨天的价格。如果今天更高就把这个差累加进profit。全部遍历完profit就是最大利润。对应的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; } }代码本身没有难度但有两个细节我要拎出来讲。第一为什么不判断是否当前持有股票因为价格差为正时贪心默认我们认为第i-1天持有、第i天卖出、当天再买回。如果此刻空仓相当于第i天买入差价收益为0。但累加的正差价依然计算进去了这不冲突——因为你第i天买入后第i1天又可能卖出逻辑链条是连续的。很好用吧但和直觉对不上我一开始也卡了很久。第二这个循环里其实隐含了当天卖完再买的操作。LeetCode允许同一天卖出和买入这个约束条件如果不成立贪心写法就要改。这个问题我在第5节会再次提到。4.2 边界情况与Integer溢出问题这道题LeetCode官方给的训练范围是prices.length在[1, 30000]之间每个价格在[0, 10000]之间。理论上最大利润不会超过30000 × 10000 3×10^8int类型Java里最大约21亿完全扛得住Python更不用担心。但真实面试场景中面试官可能会改数据范围比如价格上限改到10^9、天数改到10^5那用int就会溢出。这时建议直接用long来累计profit。另外输入为单个元素或者空数组时循环根本不会执行profit返回0这个天然正确。有人担心空数组会crash——LeetCode约束长度至少为1但如果你自己写测试用例给个空数组进去Python的range(1, 0)也不会报错返回0。Java的话需要先判空否则直接空指针。还有价格全部相同的场景比如[5,5,5,5]。遍历时每个相邻差都是0不满足prices[i] prices[i-1]profit保持0。这也符合现实逻辑价格不动没有套利空间。4.3 实测与复杂度验证时间复杂度O(n)只需要一次线性遍历空间复杂度O(1)只用了常数若干个变量。n10^5规模的数据在Python里跑一遍大概不到0.02秒Java更是毫秒级。这种复杂度在面试里属于最优解中的最优解再往下压复杂度就是在数学层面证明常数不可能更低了——因为你至少要扫一遍数组才能知道所有价格。我在本地测过一组随机生成的长序列长度100000价格在1到1000之间随机取值。贪心实现耗时约1.8毫秒Python非严格基准仅供参考。相比之下DP写法也差不多在这个量级但代码行数和思考负担明显更高。所以实际面试中如果想快速拿到正解贪心是性价比最高的路径。5. 贪心失效的场景排查什么时候不能这么干5.1 含手续费变种LeetCode714交易策略的教训贪心之所以好用建立在无摩擦交易假设上。一旦引入交易手续费结论就要打折扣。LeetCode714就是加了手续费的变体每次买卖都收一笔固定费用fee。如果你还是机械地执行只要涨价就吃差价就会出现一个问题某段差价只有0.5元但手续费要1元吃这段差价反而亏钱。更麻烦的是贪心错过的持有一段涨价后在同一笔交易里连涨好几波的情况在手续费模型下可能更优——因为你可以少付几次手续费只在一段大趋势里买卖一次。714题的正确解法是DP状态定义和122几乎一样只是卖出时现金增加要减掉feedp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i] - fee)dp[i][1] max(dp[i-1][1], dp[i-1][0] - prices[i])在我实际写题过程中有人试图对714做贪心用吃所有正差价再减去手续费的思路优化但很难控制交易次数的取舍。这个教训提醒我贪心算法对约束条件极其敏感参数一变最优性就可能崩塌。5.2 最多K笔交易变种LeetCode123与188的硬约束另一类让贪心失效的场景是给交易总数加限制。LeetCode123限定最多两笔交易LeetCode188限定最多k笔交易。此时每个正差价都吃的策略可能累积出远超k笔的交易次数超过上限后你就必须放弃某些小段收益。举个例子价格序列[1,5,2,6,8]。总共只有两个明显上涨段[1,5]和[2,6,8]但如果你把[6,8]这段吃得很细可能交易次数不够用。贪心在这里完全无法决策该放弃哪一段、保留哪一段只能靠DP加一维交易次数状态。188题的DP状态是三维第i天、交易了几次、当前是否持股。转移和122类似但每个买卖对算一次交易。复杂度O(nk)。这时候再盲目贪心面试官追问起来你会很难解释清楚。5.3 冷却期变种LeetCode309的状态迭代LeetCode309加入了一个奇怪的条件卖出股票的第二天不能买入必须冷却一天。这个约束直接破坏了贪心当天卖完当天买回的假设。你没法在上涨段的每一天都完成买入卖出循环了因为卖出后必须休息一天。309的解法仍然是DP但状态设计多了一个“冷却期状态”。经典三状态hold当日持仓的最大收益状态sold当日卖出后的最大收益rest当日冷却期后的空仓状态转移关系是rest可由hold卖出转移而来hold可由rest买入转移而来。贪心在这里彻底没戏因为它面对的不是单调可加的正收益而是一个带时序约束的动态决策。5.4 交易限制与持有约束——一个容易忽略的边界还有一个容易忽略的约束如果你手上最多只能持有k股股票而非1股贪心策略也未必最优。当k大于1时不同上涨段的差价有机会通过多仓位同时吃掉这时问题变成了一个连续时间投资组合优化问题贪心需要更精细的排序策略才能成立不能无脑累加。我的建议是遇到股票系列的题先看题目给了哪些自由再决定算法。自由越多次数无限、无手续费、无冷却、持有1股越适合贪心约束越多越需要DP统管全局。把这张约束-算法对应表记在脑子里比死记代码答案有用得多。6. 面试场上的表达顺序与常见追问6.1 如何用看得见的收益表达贪心面试时我建议你在白板上写代码前先讲思路。一个好的表达框架是第一指出这道题和121的区别在于交易次数不受限。第二直观分析任意一个非重叠的上升段都可以通过多次买卖获取收益且不会影响其他上升段。第三给出关键观察一笔跨越多个上升段的长期交易总可以拆分成多个独立的相邻上涨交易组合而中间下跌段的亏损可以被剔除。第四基于这个观察所有正相邻差值的加总就是理论利润上界而该策略恰好达到上界因此最优。这个表达顺序既包含了贪心选择性的论证也解释了上界概念面试官听完基本不会纠结你代码为什么没有更复杂的判断条件。我自己面试别人的时候最想听到的就是我能从数学性质证明它是对的而不是网上都这么写。6.2 面试官追问清单与应对思路这一节是我整理的常见追问配合相应应对策略你在面试前过一遍心里有底。追问1如果允许同一天卖出再买入你的利润会虚高吗不会。因为虚高意味着你创造了本来不存在的免费午餐。但同一天卖出再买入的净收益为0并不会增加总收益只是代码写法上不需要特判。真正的利润天花板由整体上涨幅度决定。追问2这个算法为什么不需要记录买入价格因为策略的本质是捕捉每一天的上涨。一旦今天涨就等于昨天买入今天卖出昨天买入价就是prices[i-1]。此前的持仓成本已经在之前的小段买卖中消化掉了不需要额外记录。追问3如果价格序列连续下跌贪心会不会频繁交易导致亏损不会。因为只有prices[i] prices[i-1]才执行操作下跌段complete bypass不产生任何负收益。这是贪心和网格交易这类策略最大的区别——它天然避开了亏损段。追问4能不能用差分数组的思路解释可以。差分数组diff[i] prices[i] - prices[i-1]题目要求max profit就等价于把所有正差分项累加。这其实是同一个数学事实的不同表述但听起来更高级。你可以在面试中提一句这本质上就是所有正相邻差之和。追问5这题能扩展到三维价格矩阵或者带涨跌停限制吗能但算法会发生质变。涨跌停限制会使某些天的价格被钳制相邻差不再代表真实交易收益而三维矩阵则引入了多资产协同问题。这种扩展题我建议你答到约束条件变化导致DP状态维度增加为止不要硬套贪心。6.3 我的复盘与个人体会最后聊聊我刷这道题和拿它去面试的真实感受。我第一次接触LeetCode122时其实先写的是DP因为当时对贪心的证明体系不熟。DP代码跑了通过人也安心了但总觉得不够漂亮。后来我把DP转移方程摊开、强行去发现贪心的时候才发现贪心不是灵光一闪的取巧而是DP在特定条件下退化的必然产物——这个认识比写出AC代码值钱得多。带新人刷题时我通常会让他们把股票系列的这五题121、122、123、188、309按同一套DP框架全做一遍然后在122这一题上刻意练习把DP收敛成贪心的降维思考。练完之后很多人再看到序列上累加收益的题第一反应不再是套模板而是先分析约束条件再判断算法边界。这个思维方式才是LeetCode122真正值得反复咀嚼的地方。如果你现在正准备面试或者正在系统刷题我的具体建议是不要满足于把这道题AC掉。花半小时把所有变种题的DP状态设计写一遍再用一句话总结每个变体为什么贪心失效你的收获会超过闷头刷十道简单题。至少在我访谈过的几十位候选人里能把这道题的贪心成立条件讲清楚的后面系统设计和项目深挖的表现普遍都不错——因为这说明他不是在背答案而是在理解模型。 LeetCode 122买卖股票最佳时机：贪心算法与动态规划全解析
1. 这道题到底在说什么——读懂LeetCode122的真实意图1.1 题目已经不是简单模拟而是一个决策模型很多第一次刷到LeetCode122这道买卖股票的最佳时机 II的朋友第一反应都是这跟第121题有什么区别第121题是只能买卖一次求最大利润第122题变成了可以多次买卖但你手里始终只能持有一股必须在再次买入之前把手里那只卖掉。我先说一个很容易踩进去的误区有人以为多次买卖的意思是可以无限持股、反复横跳于是上来就写状态机模拟sell买入buy卖出循环里套条件判断最后利润算得七零八落。实际上这道题的本质不是模拟交易而是在一组价格序列上做一个决策优化——每一天你要决定是持有、买入还是卖出目标函数是最终手里现金增量最大化。只要你理解了这一层贪心策略的合理性就自然而然地浮出来了。题目给的输入price数组prices[i]代表第i天的股票价格。你可以在任意一天买入一股在之后的任意一天卖出一股不限交易次数但同一时间只能持有一股。求最大总利润。注意这里还有一个隐藏条件卖出和买入可以在同一天发生也就是当天卖掉、当天买回是被允许的这个细节在后面贪心证明里非常关键。1.2 最大利润的直觉先问自己敢不敢吃每一段差价我在面试实战里遇到一个很典型的场景候选人能很快背出只要后一天比前一天高就把差价加上但被问到为什么这样就是最大时往往只会说这就是贪心啊。这句话等于没说。让我先给直觉再给证明。假设股价序列是[1, 5, 3, 6, 8]。如果你全程只做一次交易最大利润是从最低点1买入、最高点8卖出拿到7。但如果允许多次交易最聪明的做法显然是把1买进5卖出赚4然后空仓等到3买进8卖出赚5总共9。你看把一次大波段拆成两个上升段利润反而更高。为什么因为中间那段下跌5到3你躲过去了相当于你不仅赚了上升的钱还规避了回撤的损失——这在单次交易里是做不到的。所以一个朴素的策略浮出水面只要第i1天的价格比第i天高我就在第i天买入、第i1天卖出赚这一段正差价如果下跌我就不交易空仓等着。把所有正差价累加起来就是总利润。这就是LeetCode122贪心策略的核心思想。问题只在于凭什么每一段正差价都吃不会互相冲突万一我今天刚卖出明天大涨我岂不是踏空别急下面我用数学方式把这个问题彻底讲透。2. 贪心策略的数学底气为何累加正差价等于最优解2.1 交易分解一笔长持等价于连续分段我需要先证明一个核心引理任意一段从第a天买入、第b天卖出的交易其利润等于这段区间内相邻两天所有正差价之和。这句话听起来有点反直觉我举个例子验证。假设你在第a天以价格P_a买入第b天以价格P_b卖出利润是P_b - P_a。我们把区间[a, b)里的相邻价格差拆开P_b - P_a (P_{a1} - P_a) (P_{a2} - P_{a1}) ... (P_b - P_{b-1})这个恒等式是精确成立的纯粹是代数恒等变形。现在关键来了如果中间某一段相邻差值是负数比如第k天到第k1天是下跌的那么这一段的贡献是负的。如果我们在第k天卖出、第k1天再买回来就可以把这个负贡献从总利润中剔除同时不改变其他段的收益。所以把一段长持有拆成若干小段只保留上涨段、过滤下跌段得到的利润一定不低于原始单笔交易的利润。更严格一点说任意交易策略产生的总利润都可以表示为某些区间上的首尾价差之和。把每个区间按上述恒等式展开成相邻差之和再重排累加你会发现总利润就等于每个上升相邻对prices[i1] prices[i]被选择次数 × prices[i1] - prices[i]的加权和。每种合法交易策略中任意相邻两天之间的买入-卖出对最多只能被利用一次吗这里需要小心同一天卖出再买入会让相邻对的选择次数叠加但每次选择同一相邻对最多只能贡献一次正向收益因为你的持有量始终只有一股。所以任何策略的总利润不可能超过所有相邻正差价的总和。这就是贪心最优性的核心证明骨架。贪心策略把所有正差价全部吃到正好到达这个上界所以它是最优的。2.2 贪心选择性质局部最优真的能推出全局最优很多人对贪心的印象是鼠目寸光、容易局部最优但全局翻车比如经典的硬币找零问题、0-1背包问题贪心都会失效。那为什么LeetCode122偏偏能贪关键在于这个问题具有两个性质贪心选择性质和最优子结构。贪心选择性质的意思是今天看到明天涨价今天买入明天卖出这一步一定包含在某个全局最优解里。为什么因为如果你在全局最优解中没有用这组相邻交易那你必然在某一天持有股票跨越了这段上升区间。反正这段差价你早晚要赚要么现在赚要么后面以包含在长持有期的形式赚。而前面证明了把长持有拆开、剔除下跌段只会让利润更高。于是现在吃掉这段差价不会让全局解变差。最优子结构就更简单了交易决策按天推进第i天之后的最优利润只取决于剩下的价格序列和第i天之前已经赚了多少现金无关。因为题目没有持仓数量限制以外的约束每一天的决策空间是独立的。这两个性质凑齐贪心就没有翻车的余地。注意这道题能贪心的隐含前提是交易次数无上限 没有手续费 没有冷却期 可以当天买卖。一旦这些条件被改动比如加一个买入手续费贪心就可能失效。这一点我在第5节专门展开。3. 从暴力到DP再到贪心三条路线如何收敛到最优3.1 暴力搜索/状态枚举的复杂度困境先看最简单的思路每天都有三种状态——空仓、持有、以及什么都不做其实可以并入当前状态。真正麻烦的是你无法确定今天是否应该买入因为未来是未知的。第一反应是回溯枚举所有可能的交易组合对每一天决定买入、卖出还是持有。这个决策树的深度是n天每个节点三个分支总路径数量指数级。哪怕用记忆化剪枝状态维度也包含当天是否持有以及当前累计利润并不好压缩。对n10^5级别的LeetCode输入这种方案直接超时。所以我建议你第一步别写搜索先把复杂度算清楚暴力指数、O(n^2)区间贪心枚举又太笨——其实O(n^2)的枚举法存在枚举每一对买入卖出日然后被重叠区间问题卡死。这条思路走不通原因是在多次交易约束下区间之间可以嵌套也可以串联单纯枚举区间对组合会爆炸。所以我们需要状态抽象也就是动态规划。3.2 动态规划的两个状态与转移方程动态规划是这类问题最稳的通解。定义两个状态dp[i][0]第i天结束时手里没有股票所持有的最大现金数。dp[i][1]第i天结束时手里正好持有一股所持有的最大现金数。注意这里现金数不是利润而是从开始到当前天累计下来的资产净值。初始条件dp[0][0] 0第一天开始手里没股票也持有0现金dp[0][1] -prices[0]第一天就买入花掉prices[0]。转移方程dp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i])意思是第i天空仓要么前一天也空仓今天啥也不干要么前一天持股今天卖出把卖出收入加进现金。dp[i][1] max(dp[i-1][1], dp[i-1][0] - prices[i])第i天持股要么前一天也持股今天不动要么前一天空仓今天买入现金减去买入成本。答案就是dp[n-1][0]因为最后一天手里留着股票没有意义必须空仓结算利润。这个DP的时间复杂度是O(n)空间复杂度O(n)。进一步观察可以发现dp[i][0]和dp[i][1]只依赖前一天的dp[i-1][0]和dp[i-1][1]所以可以用两个滚动变量来替代整个数组空间降到O(1)。我说句实在话如果你面试做到这道题先甩DP出来是完全没毛病的。DP不仅严密而且把状态空间讲得很清晰是面试官最容易验证你思路的路线。3.3 贪心是DP在特定条件下的简化形态现在把DP的推导拿过来和贪心对照。回到刚才这两个转移方程我们把式子变个形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])如果我们用贪心思维只要prices[i] prices[i-1]就认为应该赚这段差价。这句话翻译成DP的操作等价于在第i-1天卖出如果持有然后立即在第i天买回。卖出时现金增加prices[i] - prices[i-1]买回后状态重新变为持股。本质上贪心就是DP状态中每天都强制进行一次卖出再买入、只保留正向收益的路径。从数学角度看DP的max操作允许你自由选择交易时机而贪心直接把max拆成了对每个上涨步骤的累加。因为该问题无交易次数限制、无摩擦成本每个上涨段的收益是彼此独立的max整体可以分解为逐段max再加和。所以贪心是在DP更宽松条件下的解析解。我建议你把这个关系写在笔记里先秒杀DP再用DP解释贪心为什么成立。这比直接背一个三行贪心代码要有说服力得多。4. 代码落地实现细节、边界与复杂度验证4.1 核心实现你真的只需要三行LeetCode122的贪心实现极短我甚至见过有人用一行reduce写完。但我们写工程代码还是以可读性优先。我手写一版最标准的Python实现def maxProfit(prices: List[int]) - int: profit 0 for i in range(1, len(prices)): if prices[i] prices[i - 1]: profit prices[i] - prices[i - 1] return profit循环从第1天开始每次比较今天的价格和昨天的价格。如果今天更高就把这个差累加进profit。全部遍历完profit就是最大利润。对应的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; } }代码本身没有难度但有两个细节我要拎出来讲。第一为什么不判断是否当前持有股票因为价格差为正时贪心默认我们认为第i-1天持有、第i天卖出、当天再买回。如果此刻空仓相当于第i天买入差价收益为0。但累加的正差价依然计算进去了这不冲突——因为你第i天买入后第i1天又可能卖出逻辑链条是连续的。很好用吧但和直觉对不上我一开始也卡了很久。第二这个循环里其实隐含了当天卖完再买的操作。LeetCode允许同一天卖出和买入这个约束条件如果不成立贪心写法就要改。这个问题我在第5节会再次提到。4.2 边界情况与Integer溢出问题这道题LeetCode官方给的训练范围是prices.length在[1, 30000]之间每个价格在[0, 10000]之间。理论上最大利润不会超过30000 × 10000 3×10^8int类型Java里最大约21亿完全扛得住Python更不用担心。但真实面试场景中面试官可能会改数据范围比如价格上限改到10^9、天数改到10^5那用int就会溢出。这时建议直接用long来累计profit。另外输入为单个元素或者空数组时循环根本不会执行profit返回0这个天然正确。有人担心空数组会crash——LeetCode约束长度至少为1但如果你自己写测试用例给个空数组进去Python的range(1, 0)也不会报错返回0。Java的话需要先判空否则直接空指针。还有价格全部相同的场景比如[5,5,5,5]。遍历时每个相邻差都是0不满足prices[i] prices[i-1]profit保持0。这也符合现实逻辑价格不动没有套利空间。4.3 实测与复杂度验证时间复杂度O(n)只需要一次线性遍历空间复杂度O(1)只用了常数若干个变量。n10^5规模的数据在Python里跑一遍大概不到0.02秒Java更是毫秒级。这种复杂度在面试里属于最优解中的最优解再往下压复杂度就是在数学层面证明常数不可能更低了——因为你至少要扫一遍数组才能知道所有价格。我在本地测过一组随机生成的长序列长度100000价格在1到1000之间随机取值。贪心实现耗时约1.8毫秒Python非严格基准仅供参考。相比之下DP写法也差不多在这个量级但代码行数和思考负担明显更高。所以实际面试中如果想快速拿到正解贪心是性价比最高的路径。5. 贪心失效的场景排查什么时候不能这么干5.1 含手续费变种LeetCode714交易策略的教训贪心之所以好用建立在无摩擦交易假设上。一旦引入交易手续费结论就要打折扣。LeetCode714就是加了手续费的变体每次买卖都收一笔固定费用fee。如果你还是机械地执行只要涨价就吃差价就会出现一个问题某段差价只有0.5元但手续费要1元吃这段差价反而亏钱。更麻烦的是贪心错过的持有一段涨价后在同一笔交易里连涨好几波的情况在手续费模型下可能更优——因为你可以少付几次手续费只在一段大趋势里买卖一次。714题的正确解法是DP状态定义和122几乎一样只是卖出时现金增加要减掉feedp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i] - fee)dp[i][1] max(dp[i-1][1], dp[i-1][0] - prices[i])在我实际写题过程中有人试图对714做贪心用吃所有正差价再减去手续费的思路优化但很难控制交易次数的取舍。这个教训提醒我贪心算法对约束条件极其敏感参数一变最优性就可能崩塌。5.2 最多K笔交易变种LeetCode123与188的硬约束另一类让贪心失效的场景是给交易总数加限制。LeetCode123限定最多两笔交易LeetCode188限定最多k笔交易。此时每个正差价都吃的策略可能累积出远超k笔的交易次数超过上限后你就必须放弃某些小段收益。举个例子价格序列[1,5,2,6,8]。总共只有两个明显上涨段[1,5]和[2,6,8]但如果你把[6,8]这段吃得很细可能交易次数不够用。贪心在这里完全无法决策该放弃哪一段、保留哪一段只能靠DP加一维交易次数状态。188题的DP状态是三维第i天、交易了几次、当前是否持股。转移和122类似但每个买卖对算一次交易。复杂度O(nk)。这时候再盲目贪心面试官追问起来你会很难解释清楚。5.3 冷却期变种LeetCode309的状态迭代LeetCode309加入了一个奇怪的条件卖出股票的第二天不能买入必须冷却一天。这个约束直接破坏了贪心当天卖完当天买回的假设。你没法在上涨段的每一天都完成买入卖出循环了因为卖出后必须休息一天。309的解法仍然是DP但状态设计多了一个“冷却期状态”。经典三状态hold当日持仓的最大收益状态sold当日卖出后的最大收益rest当日冷却期后的空仓状态转移关系是rest可由hold卖出转移而来hold可由rest买入转移而来。贪心在这里彻底没戏因为它面对的不是单调可加的正收益而是一个带时序约束的动态决策。5.4 交易限制与持有约束——一个容易忽略的边界还有一个容易忽略的约束如果你手上最多只能持有k股股票而非1股贪心策略也未必最优。当k大于1时不同上涨段的差价有机会通过多仓位同时吃掉这时问题变成了一个连续时间投资组合优化问题贪心需要更精细的排序策略才能成立不能无脑累加。我的建议是遇到股票系列的题先看题目给了哪些自由再决定算法。自由越多次数无限、无手续费、无冷却、持有1股越适合贪心约束越多越需要DP统管全局。把这张约束-算法对应表记在脑子里比死记代码答案有用得多。6. 面试场上的表达顺序与常见追问6.1 如何用看得见的收益表达贪心面试时我建议你在白板上写代码前先讲思路。一个好的表达框架是第一指出这道题和121的区别在于交易次数不受限。第二直观分析任意一个非重叠的上升段都可以通过多次买卖获取收益且不会影响其他上升段。第三给出关键观察一笔跨越多个上升段的长期交易总可以拆分成多个独立的相邻上涨交易组合而中间下跌段的亏损可以被剔除。第四基于这个观察所有正相邻差值的加总就是理论利润上界而该策略恰好达到上界因此最优。这个表达顺序既包含了贪心选择性的论证也解释了上界概念面试官听完基本不会纠结你代码为什么没有更复杂的判断条件。我自己面试别人的时候最想听到的就是我能从数学性质证明它是对的而不是网上都这么写。6.2 面试官追问清单与应对思路这一节是我整理的常见追问配合相应应对策略你在面试前过一遍心里有底。追问1如果允许同一天卖出再买入你的利润会虚高吗不会。因为虚高意味着你创造了本来不存在的免费午餐。但同一天卖出再买入的净收益为0并不会增加总收益只是代码写法上不需要特判。真正的利润天花板由整体上涨幅度决定。追问2这个算法为什么不需要记录买入价格因为策略的本质是捕捉每一天的上涨。一旦今天涨就等于昨天买入今天卖出昨天买入价就是prices[i-1]。此前的持仓成本已经在之前的小段买卖中消化掉了不需要额外记录。追问3如果价格序列连续下跌贪心会不会频繁交易导致亏损不会。因为只有prices[i] prices[i-1]才执行操作下跌段complete bypass不产生任何负收益。这是贪心和网格交易这类策略最大的区别——它天然避开了亏损段。追问4能不能用差分数组的思路解释可以。差分数组diff[i] prices[i] - prices[i-1]题目要求max profit就等价于把所有正差分项累加。这其实是同一个数学事实的不同表述但听起来更高级。你可以在面试中提一句这本质上就是所有正相邻差之和。追问5这题能扩展到三维价格矩阵或者带涨跌停限制吗能但算法会发生质变。涨跌停限制会使某些天的价格被钳制相邻差不再代表真实交易收益而三维矩阵则引入了多资产协同问题。这种扩展题我建议你答到约束条件变化导致DP状态维度增加为止不要硬套贪心。6.3 我的复盘与个人体会最后聊聊我刷这道题和拿它去面试的真实感受。我第一次接触LeetCode122时其实先写的是DP因为当时对贪心的证明体系不熟。DP代码跑了通过人也安心了但总觉得不够漂亮。后来我把DP转移方程摊开、强行去发现贪心的时候才发现贪心不是灵光一闪的取巧而是DP在特定条件下退化的必然产物——这个认识比写出AC代码值钱得多。带新人刷题时我通常会让他们把股票系列的这五题121、122、123、188、309按同一套DP框架全做一遍然后在122这一题上刻意练习把DP收敛成贪心的降维思考。练完之后很多人再看到序列上累加收益的题第一反应不再是套模板而是先分析约束条件再判断算法边界。这个思维方式才是LeetCode122真正值得反复咀嚼的地方。如果你现在正准备面试或者正在系统刷题我的具体建议是不要满足于把这道题AC掉。花半小时把所有变种题的DP状态设计写一遍再用一句话总结每个变体为什么贪心失效你的收获会超过闷头刷十道简单题。至少在我访谈过的几十位候选人里能把这道题的贪心成立条件讲清楚的后面系统设计和项目深挖的表现普遍都不错——因为这说明他不是在背答案而是在理解模型。