type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给定prices数组。每一天可以决定要购买和/或出售股票。
在任何时间最多持有一股。但可以购买它,然后立即同一天出售。
返回可以实现的最大利润。

例1:
例2:
例3:
解法一:贪心 (推荐)
把价格画成折线,你能做不限次数的交易。
最赚钱的做法其实特别朴素:凡是今天比昨天贵,就把这段差价赚到手。
可以理解成:在每一段连续上升里,从谷底买、在峰顶卖。
而把所有上升段的增量相加,等价于一路“昨天买今天卖、今天再买明天卖……”,收益完全一样。
这背后是一个“交换论证”:任何把一段上升拆成多笔/合成一笔,利润都一样;而在下降段持仓只会拉低收益,不如空仓等待下一次上升。
复杂度
- 时间 O(n)
- 空间 O(1)
解法二:峰谷法
用显式找“低买高卖”的边界。
把图像里每段局部谷 → 局部峰的差值加起来。
它和解法一完全等价,只是把“所有正差”的表达换成了“找每段低点和高点”的语义,更贴合“买一次卖一次”的思维。
复杂度
- 时间 O(n)
- 空间 O(1)
解法三:状态机 DP(通用解法)
把每天的选择抽象成两个状态:
hold:到今天为止,手里持有一股时的最大利润;
cash:到今天为止,手里空仓时的最大利润。
转移很自然:
- 今天空仓可以延续空仓,或者卖出今天的价:
cash = max(cash, hold + price)
- 今天持仓可以延续持仓,或者买入今天的价:
hold = max(hold, cash - price)
注意更新顺序要用“昨天的 cash/hold”来推今天的,避免相互污染。
复杂度
- 时间 O(n)
- 空间 O(1)
注:状态机 DP是通用解法,更“可拓展”,比如要加入手续费、冷冻期、交易次数上限等限制时,直接在状态里加维度即可。
解法四:递归DP
把“第
i 天、是否还能买(或是否正持仓)”当作状态,穷举“买/卖/跳过”三类决策。暴力递归会大量重复子问题;加缓存就能把复杂度降到线性。复杂度
- 时间 O(n)(每个
(i, can_buy)状态只算一次)
- 空间 O(n)(递归栈 + 记忆表)
解法五:表格DP
和解法三是同样的状态/转移,只是显式开一个
dp[i][buy] 的二维表,从后往前把答案填出来。 复杂度
- 时间 O(n)
- 空间 O(n)
解法六:表格DP的空间优化
二维表只依赖“下一天”的值,把
dp[i+1][*] 压成两个变量即可,代码更紧凑。复杂度
- 时间 O(n)
- 空间 O(1)
- Author:Fan Luo
- URL:https://fanluo.me/article/leetcode-122-买卖股票的最好时间-ii
- Copyright:All articles in this blog adopt BY-NC-SA agreement. Please indicate the source!
上一篇
[Leetcode 121] 买卖股票的最佳时机
下一篇
[Leetcode 123] 买卖股票的最佳时机 III