[Leetcode 122] 买卖股票的最好时间 II

type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给定prices数组。每一天可以决定要购买和/或出售股票。
在任何时间最多持有一股。但可以购买它,然后立即同一天出售。
返回可以实现的最大利润。
notion image
 
例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)
上一篇
[Leetcode 121] 买卖股票的最佳时机
下一篇
[Leetcode 123] 买卖股票的最佳时机 III