力扣122题：买卖股票最佳时机2的贪心算法与动态规划全解析

刷过股票买卖系列的同学，对力扣122题“买卖股票的最佳时机2”应该都不陌生。这道题在面试中出现频率很高，但它和121题“只能买卖一次”的设定有很大不同：你可以进行多次交易，只要手里最多持有一股。很多人在第一次做这题时会觉得“这还不简单，低买高卖就行”，可真要动手写代码，又说不清每一次买卖之间怎么衔接、贪心到底贪在哪。这篇文章我会把两种主流的解法——贪心算法和动态规划——从推导到实现完整拆开来讲，连同边界条件、易错点和面试延伸一起覆盖，适合正在刷题准备校招/社招的开发者，也适合想彻底吃透这题的朋友。

1. 题目解读与核心思路：为什么“多次交易”比“单次交易”更好拆

1.1 读懂题设中的三个隐藏条件

先看题目的原始描述：给定一个数组prices，其中prices[i]表示某只股票第 i 天的价格。在每一天，你可以决定是否买入和/或卖出股票，但在任何时候，最多只能持有这股股票的一股。计算你能获得的最大利润。

这段话看着平铺直叙，其实包含了三个关键约束：

• 第一，“在每一天，你可以决定是否买入和/或卖出”，这句话意味着同一天内既卖出又买入是允许的。卖出旧仓位，再立刻买入新仓位，这在实际交易中叫“换仓”，在这里是合法的操作。这个条件容易被忽略，但在推导贪心时非常重要。
• 第二，“任何时候最多只能持有这股股票的一股”，这限制了你不能在同一天先买两股再分批卖，也不能在已经持仓的情况下继续加仓。也就是说，你的仓位状态只有两种：空仓或持仓。
• 第三，目标是“最大利润”，利润等于所有已实现交易的卖出价减买入价之和。与121题不同，这里不限制交易次数，所以需要从整体收益最大化出发。

这三个条件共同决定了：这道题的本质不再是一次性决策，而是一连串买卖决策的组合优化问题。

1.2 第一步“暴力”为什么不可行

在没有接触过这题的时候，很多人的第一反应是枚举所有可能的买卖组合：选择若干个买入点，再选择若干个卖出点，保证买卖交替、先买后卖。如果直接枚举，每个价格点都会面临买入、卖出、观望三种选择，整个决策树的规模是 O(3ⁿ) 级别的。就算对 n 只有几万的情况，也会直接超时。

我见过有同学写回溯枚举每一对买卖区间，然后用区间覆盖的思路去重，能跑通小规模测试，但遇到 n = 10⁵ 的用例就力不从心了。其实这道题有个非常巧妙的观察：既然可以无限次交易，且每天都可以买卖，那么一笔长期的买卖可以被拆成许多段短期的“每天买卖”来看待，而利润不变甚至有可能会更高。

1.3 把“多笔交易”拆成“相邻价格差”是整题的钥匙

假设价格序列是 [7, 1, 5, 3, 6, 4]。如果按最简单的做法，在第 1 天买入 1，第 3 天卖出 5，赚 4；再在第 3 天买入 5（这里用同一天卖出再买入），第 5 天卖出 6，又赚 1。总利润 5。

但如果把每一天的价差都算出来：-6、+4、-2、+3、-2。把其中所有正数相加，得到 4 + 3 = 7，居然比刚才的 5 还大。为什么？因为上面的拆法还把一天的价格波动“切碎”了：从 1 到 5 之间其实经历了 1 → 5 的上涨，但更细地看 1 → 5 这步涨了 4，5 → 3 跌了 2，3 → 6 又涨了 3。如果只看涨的部分，就是 4 + 3 = 7；而一段完整的“持有期”里，下跌的两块钱被“吞掉”了。

这里得到的核心思想是：在允许无限次交易的条件下，利润可以看作所有正差值的累加。你不需要预测未来的最高点，只需要知道今天比昨天贵还是便宜。今天的价差为正，说明昨天买入、今天卖出能赚到钱，就值得做；为负或零，就不要参与。这就是贪心算法的雏形。

2. 贪心算法：为什么“只赚上涨段”就是全局最优

2.1 贪心策略的直观推导

把股票价格看成一幅折线图。你在折线上可以任意选择买入点和卖出点，但必须保证每次买入在卖出之前，且手里最多一股。直观上，所有人都希望在波谷买入、波峰卖出。但问题是，你不可能预知未来，怎么知道今天是不是波谷？明天会不会更高？

如果抛开“预知未来”的顾虑，单从结果上看，一段完整的上涨区间（比如 1 → 5 → 6）里，最优做法是什么？不是在第 1 天买、第 3 天卖，而是在上涨的每一天都赚走当天的价差。从 1 涨到 5，你通过“前一天买、今天卖”赚 4；从 5 涨到 6，你又可以“昨天买、今天卖”赚 1。你不需要等到最高点才卖，因为每天卖完再买入，相当于永远持有在这段上涨趋势中，但把浮盈全部落袋了。

数学上更严谨一点：假设你在第 i 天买入、第 j 天卖出（j > i），这笔交易的利润是prices[j] - prices[i]。这个值其实等于：

prices[j] - prices[i] = (prices[i+1] - prices[i]) + (prices[i+2] - prices[i+1]) + ... + (prices[j] - prices[j-1])

也就是说，任意一笔跨越多天的交易利润，等于经过的所有相邻两天价格差的和。如果中间有些天是下跌的，那这些负差就会减少总利润。而你完全可以在每次负差出现之前先卖出，等跌完再买回来，这样就能避开所有负差。因此，把所有正差累加起来，就是能获得的最大利润。

2.2 贪心代码实现与复杂度分析

代码非常简单，我用 Python 写一版直观的：

def maxProfit(prices): profit = 0 for i in range(1, len(prices)): diff = prices[i] - prices[i - 1] if diff > 0: profit += diff return profit

如果你愿意，甚至可以压缩成一行：

def maxProfit(prices): return sum(max(prices[i] - prices[i - 1], 0) for i in range(1, len(prices)))

时间复杂度 O(n)，只需要一次遍历；空间复杂度 O(1)，只用了常数个变量。这个效率已经是最优了，因为至少得读一遍价格数组才能算出利润。

我测试过几组典型用例：

• prices = [7, 1, 5, 3, 6, 4]，结果为 7，与预期一致。
• prices = [1, 2, 3, 4, 5]，结果为 4，等价于第 0 天买、第 4 天卖，只赚 4；但贪心拆成四段，每天赚 1，加起来还是 4。这两种做法的“结果”一样。
• prices = [5, 4, 3, 2, 1]，所有差值为负，结果 0，这意味着最佳策略是全程不交易。
• prices = [1, 3, 2, 4, 5, 4]，差值为 +2、-1、+2、+1、-1，正差和为 2 + 2 + 1 = 5。你可以在 1 买 3 卖，2 买 5 卖，总利润 5。

有人会问：如果出现连续几天的上涨，贪心拆成每天买卖，会不会因为“今天卖完再买入”而违反“手里最多一股”的约束？并不会。今天的卖出发生在买入之前，实际顺序是“昨天买了今天卖 → 今天再买明天再卖”，每一时刻最多持有一股，完全合法。只是从结果上看，你每天都参与了市场，但每天收盘后仓位又回到了空仓再建仓的状态，所以本质上是一串独立的“隔日交易”，这也正是贪心能成立的原因。

2.3 关于“贪心只有一个维度”的一点澄清

我在实际讲解过程中发现，很多人对这种贪心的疑虑集中在一点：如果只看相邻两天，那在 1 买入、在 6 卖出，岂不是能赚 5 而不是 4+1=5？其实这两种做法的总利润是一样大的，都吃到了整段上涨的总涨幅。差别在于：长线做法把上涨过程中的浮动利润放在账面上，中间没有落袋；而短线贪心把每一天的涨幅都“收割”了，中间一旦出现下跌，还能提前止损，反而更有优势。

所以这道题的贪心，并不是“预测哪天涨停”，而是基于一个数学事实：任何上涨段的总涨幅等于该段内所有相邻正差之和。只要把相邻正差全部吃掉，就能赚到所有上涨段的钱。这其实就是把“低买高卖”这个直觉变成了可执行的算法。你不需要知道波峰在哪，因为每天的高点就是当天相对昨天的增量；也不需要担心卖早了，因为卖完还能立刻买回来。

3. 动态规划解法：状态机思路才是面试官更想听的

3.1 为什么讲完贪心还要学动态规划

既然贪心代码只有几行，为什么还要学动态规划？因为在真正的面试中，很多面试官不会满足于“你会写贪心”。他们会追问：如果加一个交易手续费怎么办？如果限制最多只能做 k 笔交易怎么办？如果卖出后第二天才能买（冷冻期）怎么办？一旦加了这些限制，“把所有正差加起来”就不再成立，你需要的是一套能处理更复杂约束的通用框架，这就是动态规划。

另外，动态规划的“状态机”思路，在这类问题上非常有代表性。理解清楚dp[i][0]和dp[i][1]的含义，之后遇到股票买卖家族的变体，几乎都能套同一套模板，只是转移方程略作调整。这也是我特别推荐把这道题的动态规划解法吃透的原因。

3.2 状态定义与转移方程推导

对动态规划来说，第一步永远是定义状态。这里我们定义：

• dp[i][0]表示第 i 天结束时，手里不持有股票，能获得的最大利润。
• dp[i][1]表示第 i 天结束时，手里持有一支股票，能获得的最大利润。

这里有一个常见的困惑：“手里持有股票时，利润为什么是负数？”你可以把“买入股票”看作花掉了一笔现金，这笔现金记为负的利润，后续卖出时再把现金加回来。把问题抽象成“现金收益视角”后，状态转移就非常自然了。

第 i 天结束时，手里没有股票，可能有两种来路：

1. 前一天本来就没有股票，今天也没买，那么利润继承自dp[i-1][0]。
2. 前一天持有股票，今天把它卖掉了，那么利润等于dp[i-1][1] + prices[i]。

所以：

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

第 i 天结束时，手里持有一支股票，也可能有两种来路：

1. 前一天本来就持有股票，今天继续持有，没有新操作，利润继承自dp[i-1][1]。
2. 前一天没有股票，今天买入了一支，那么利润等于dp[i-1][0] - prices[i]。

所以：

dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])

两个方程合起来，就是这道题在“无限次交易”条件下的完整状态转移过程。你可能会注意到，这里没有任何“次数”维度，原因很简单：交易次数不受限制，所以不需要记录已经交易了几次。一旦你去做限制 k 次的变体，就得把状态从二维扩成三维，增加一维记录交易次数。

3.3 初始化、循环与返回值

初始化第 0 天：

dp[0][0] = 0 dp[0][1] = -prices[0]

第一天如果你买入股票，利润就是负的当天价格（因为花出去了）；如果没买，利润就是 0。注意第一天一定不能卖出，因为还没买入过任何股票。

循环从 i = 1 开始，一直到 n - 1。最后一天结束时，手里肯定不应该还拿着股票，因为留着股票没有任何额外收益（题目不要求最后一天必须卖出，但持有不卖不会增加利润，反而占用了应该兑现的现金，所以最大值必然在dp[n-1][0]）。我们返回dp[n-1][0]即可。

完整代码：

def maxProfit(prices): n = len(prices) if n == 0: 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]

跑一遍[7, 1, 5, 3, 6, 4]，动态规划数组的变化如下：

最终结果是 5？等等，这跟贪心算出来的 7 不一样？其实这里是我为了演示随便列的一组“中间利润值”有误导性：dp[i][0]是“第 i 天结束时手里没股票的最大利润”，第 2 天结束可以不卖，也可以价格 5 卖掉，但第 2 天最高利润是卖出 4；第 4 天结束时如果手里没股票，最大利润是 5，这看着像只做了一笔交易 1→6。但我们允许反复买卖，为什么 dp 只给出 5 而不是 7？

这里要注意：动态规划的状态里，第 4 天结束时手里没股票的最大利润，确实不止 5。我们看递推：第 4 天prices[4] = 6，dp[4][0] = max(dp[3][0], dp[3][1] + 6)。dp[3][1]是第 3 天结束时手里持股的最大利润，应该是max(dp[2][1], dp[2][0] - 3)=max(-1, 4 - 3)= 1，所以dp[4][0] = max(4, 1 + 6) = 7，不是 5。我前面的表里dp[3][1]写成了 -1，应该修正为 1。这说明手动推演时一定要仔细，但最终结果确实和贪心一致为 7。

3.4 空间优化：滚动数组把二维压成一维

上面代码用一个 n × 2 的二维数组存状态，空间复杂度 O(n)。其实在计算第 i 天时，只会用到第 i-1 天的两个值，完全可以用两个变量滚动更新：

def maxProfit(prices): n = len(prices) if n == 0: return 0 not_hold = 0 # dp[i][0] hold = -prices[0] # dp[i][1] for i in range(1, n): # 注意这里要先保存旧值，避免覆盖后影响另一个状态的计算 prev_not_hold = not_hold prev_hold = hold not_hold = max(prev_not_hold, prev_hold + prices[i]) hold = max(prev_hold, prev_not_hold - prices[i]) return not_hold

空间复杂度降为 O(1)，时间复杂度不变。如果你觉得每次改两个临时变量麻烦，也可以用一个二元组来写：

def maxProfit(prices): if not prices: return 0 cash, hold = 0, -prices[0] for price in prices[1:]: cash, hold = max(cash, hold + price), max(hold, cash - price) return cash

Python 元组的右值会先用旧cash和旧hold计算完，再统一赋值，所以不需要担心覆盖问题。这也是我平时比较推荐的一种写法。

3.5 两种解法的对比与选择

从“为了解题通过”的角度，贪心足够了；但从“通过面试”的角度，动态规划思路通常更能体现算法功底。我的习惯是面试时先给出贪心最优解，然后主动补充“如果加交易费，我会切换到状态机 DP”，这样既能展示效率，又能展示知识体系的完整性。

4. 边界条件与常见坑：提交前必须检查的几件事

4.1 空数组和单元素数组

prices为空数组或只有一个元素时，无法完成任何一笔“先买后卖”的交易，最大利润是 0。贪心解法里，range(1, len(prices))天然不会进入循环，返回 0，所以不用额外判断。动态规划解法则必须加空数组判断，否则prices[0]会越界。

输入: [] → 输出: 0 输入: [5] → 输出: 0

这两个用例看着简单，却是很多人提交第一版代码时最容易挂的地方。尤其是用动态规划的同学，n == 0的判断一定不能漏。

4.2 全部上涨和全部下跌

全部上涨时，比如[1, 2, 3, 4, 5]，贪心累加每天的正差，得到 4；动态规划走到最后也会得到 4。这里再多说一句：虽然你实际可以第 0 天买、第 4 天卖，赚的同样是 4，但“每天买每天卖”和“持有一整段”的结果完全相等，这正是因为整段上涨没有出现负差。全部下跌时，比如[5, 4, 3, 2, 1]，贪心和动态规划都会返回 0，最优策略是全程观望，一分钱别赚也别亏。

4.3 反复横跳的价格波动

[1, 3, 2, 4, 5, 4]这种用例最能体现贪心的价值：如果你试图找到“绝对最低点”和“绝对最高点”，可能会选 1 买入、5 卖出，利润 4；但如果把中段 2 → 4 这段涨也吃进去，1 买 3 卖，2 买 5 卖，总利润 5。这就是“赚走所有上涨段”的好处，也是无限次交易和单次交易最本质的区别。

4.4 一个常见的经典错误：滚动数组更新顺序

如果你写滚动数组版本时不注意赋值顺序，很容易出现错误。比如：

# 错误的示例 not_hold = max(not_hold, hold + price) hold = max(hold, not_hold - price)

第一行更新完not_hold后，第二行not_hold已经变成第 i 天的值了，再拿它去算“第 i 天买入后的持股利润”，就相当于在同一天先卖后买还叠加了今天的利润，会导致结果偏大。正确做法是用旧值计算，或者利用 Python 元组赋值的特性一次性算完。这个问题我在代码 review 时见过不止一次，属于非常典型的状态覆盖 bug。

4.5 关于“同一天卖出再买入”的合法性再验证

有些同学会担心，贪心把每天的正差累加，会不会在逻辑上出现“先卖后买”导致异常？比如昨天买入，今天先卖再买，明天再卖。这在现实中是合规的，力扣题解里也明确说明每天可以同时进行买入和卖出操作。如果理解上有障碍，可以换个角度：把这种操作看作“我把昨天的持仓平掉，然后立刻以今天的价格重新建仓”，本质上没有新增资金投入，只是让持仓成本变成了今天的价格。所以不必把这个操作当成真实交易中的“T+0”问题来纠结。

4.6 测试用例速查表

拿到这些用例在本地跑一遍，基本可以覆盖绝大多数情况。特别是[2, 1, 2, 0, 1, 2]这种包含两段分离上涨的数组，能有效检验你的代码是否把两段利润都吃到了。

5. 面试延伸：从这道题到股票买卖系列变体的知识迁移

5.1 变体一：每笔交易收取固定手续费

假设每次买入或卖出时都要支付一笔固定手续费fee，那么利润就会被摊薄。这时候不能无脑累加所有正差，因为如果某次上涨带来的利润还覆盖不了手续费，那么这次交易做了反而亏。处理办法是在状态转移中扣掉费用：

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] - fee)

就是在买入时多扣一次手续费，这样每次完整交易实际上承担了一次手续费成本。只要改为动态规划，代码改动非常小，这也是状态机模型的最大优势。

5.2 变体二：卖出后的第二天才能买入（冷冻期）

冷冻期意味着你在卖出后的一天内无法买入，所以状态需要增加一个“冷静期”维度，或者把卖出和买入的状态拆得更细。常见做法是定义三种状态：空仓可买、持仓、空仓冷冻。每次从“持仓卖出”只能转到“空仓冷冻”，冷冻期结束后才能进入“空仓可买”，这样状态转移方程就变成了三态转移。核心框架仍然是这题的思路。

5.3 变体三：最多只能交易 k 次

如果要限制交易次数，就需要在状态里增加一个维度表示“已经完成的交易次数”。dp[i][k][0]表示第 i 天结束、已经完成了 k 次交易、手里没有股票的最大利润；dp[i][k][1]表示手里有股票。买入时交易次数不变（因为买入不算完成交易），卖出时交易次数加一。这样状态数量就从 2n 变成 2nk，时间复杂度 O(nk)。对于 k 很大的情况，还能用一些优化把复杂度压回 O(n)，但那是后话。

5.4 为什么这道题值得反复揣摩

从一个只写贪心几行代码的题目，能自然引出“状态机 DP”和“多维状态扩展”，这道题在算法面试中的价值就在于此。我见过不少同学把 121、122、123、309、714 这五道股票题按顺序刷一遍，理解层次明显不一样：最开始只会背代码，后来能讲出状态如何转移，再后来看到新变体也能独立设计状态。这种“用一道题建立一类题的知识框架”的方式，比盲目刷几十道不相关题目要高效得多。

我在实际面试中遇到过类似的问题，面试官从“不限交易次数”一路追问到“如果限制最多两笔交易”，我直接把状态数组升级成三维，当场推转移方程，对方比较认可。所以如果你时间有限，建议至少把 122 题贪心和 DP 两种解法都吃透，并且能现场讲清楚为什么贪心能拿全局最优。

这个项目后续还可以继续扩展：你可以把上面的三种变体都自己实现一遍，再对比不同约束下状态数量的变化；也可以用这个题练手写单元测试，把边界用例固化成测试集。无论你是刚开始刷题的初学者，还是准备面试的求职者，122 题都是一块非常好的“试金石”。刷过三道五次之后，你会发现自己的状态机思维会明显上一个台阶。