题目
LC 121 买卖股票的最佳时机：给定数组
prices，
prices[i] 是第
i 天的股价。选择一个低点
买入、一个更高的点
卖出（只能买卖
一次，且必须先买后卖），计算最大利润。无法获利则返回
0（干脆不买）。
输入: prices = [7,1,5,3,6,4]
输出: 5 （第 1 天以 1 买入、第 4 天以 6 卖出，6 - 1 = 5）
输入: prices = [7,6,4,3,1]
输出: 0 （全程下跌，不买）
：同一组价格，可以
无限次交易（多次买卖），但仍须先买后卖、
手里最多持一股（买了才能再买下一次）。求最大利润。
输入: prices = [7,1,5,3,6,4]
输出: 7 （1→5 赚 4，3→6 赚 3，共 7）
输入: prices = [1,2,3,4,5]
输出: 4 （连续持有 1→5 即可，频繁买卖不加分）
两道题共享同一张
状态机：121 是"只许一笔"的极简单变量扫描，122 是"无限笔"的双状态 DP —— 而 122 的 DP 恰好塌缩成"所有正差之和"的贪心。把这两台机器看清，追问链上的 309（冷冻期）、714（手续费）、123（限两笔）、188（限 k 笔）全是
改转移方程，不是换思路。
一、LC 121 核心洞察：minPrice 是在等"最便宜的昨天"
暴力的 121 枚举所有 (买, 卖) 对：
O(n²)。压缩的关键是换一个提问方式：
不枚举"哪天买"，而是逐天问"今天卖，最赚能多少"。
在第
d 天卖出，买入日必然选
0..d-1 里
最便宜的那天 —— 于是只需要两个变量：
minPrice：截至昨天的历史最低价（我手里最便宜的那笔买入机会）；best：所有"今天卖出"里的最大利润。
def maxProfit(prices):
min_price, best = prices[0], 0
for p in prices[1:]:
best = max(best, p - min_price) # 先按今天的价格卖一把
min_price = min(min_price, p) # 再把今天并入历史最低价
return best
两个变量都
单调：
minPrice 只下台阶、
best 只上坡 —— 大多数日子两件事都不发生（动画里的"路过帧"），动的那几帧才是答案的来路。全程下跌时
candidate 恒为负数，
best 停在
0，语义就是
干脆不买 —— 这是 121 的合法答案，也是"最大利润"与"最大差值"的分界。
一句话立意：
121 不是找最低点，是等最低点被后来的高价兑现。
二、LC 122 核心洞察：贪心吃正差 ≡ cash/hold 状态机
可以无限次买卖后，出现两条路：
贪心：每一段
上坡都吃下，下坡空仓躲过 —— 利润 = 所有正差之和：
def maxProfit(prices):
return sum(max(0, b - a) for a, b in zip(prices, prices[1:]))
[7,1,5,3,6,4]：差值序列
-6, +4, -2, +3, -2，正差和 =
4 + 3 = 7。为什么"天天吃正差"不违反"手里最多一股"？因为相邻正差可以
无缝拼接：
+4 等价于 1→5 一笔，中途没有下坡可躲；把连续上坡拆成逐日小额交易，总和不变。
状态机 DP：每天收盘后世界只有两种状态 ——
cash：手里没票的最大利润；hold：手里有票的最大利润。
转移只有两行（
price 是今天的价格，右侧全是
昨天的值）：
cash = max(空仓不动 prevCash, 昨天持股今天卖 prevHold + price)
hold = max(持股不动 prevHold, 昨天空仓今天买 prevCash - price)
开局第 0 天：
cash = 0、
hold = -prices[0]（建仓了，钱变成票、利润为负）。终态答案是
cash ——
持股未变现不算利润。
def maxProfit(prices):
cash, hold = 0, -prices[0]
for p in prices[1:]:
cash = max(cash, hold + p)
hold = max(hold, cash - p) # 先卖后买同日允许，等价于继续持有
return cash
两条路谁对？动画每帧并排给出
greedy 与
cash ——
逐帧相等。这不是巧合：把 DP 展开，
cash 每次超过前值的增量恰是当天的正差。贪心是这台状态机"每天必做决定"的特例，DP 是贪心的机器证明。面试写哪个都对，但
能说出两者等价才是这题的满分答案。
三、动画怎么看
121 动画（
algo-viz--lc121）：顶部是价格格子行 —— 当前日金框（
today 指针在上）、历史最低价所在格绿框（
min 指针在下）；中部横幅给出"卖一把"的现场打分：
price - minPrice = candidate 与
best 比大小，决定刷新还是路过；底部面板是双变量
minPrice / candidate / best —— 盯住
minPrice 只下台阶、
best 只上坡。默认
[7,1,5,3,6,4]：第 1 天破底、第 2 与第 4 天两刷 best，答案 5。
122 动画（
algo-viz--lc122）：顶部同样是价格格子行，但
相邻格之间挂着差值徽章 —— 上坡绿
+4、下坡灰
-2，贪心吃不吃这段一眼可见；中部是
cash / hold 两个状态框，转移方程的获胜方描金；底部面板并排
greedy / cash / hold 三列 ——
前两列逐帧相等，贪心与状态机同一条命。默认同数组：吃下
+4 与
+3，答案 7。
两个动画共用同一组默认价格，看完 121 再看 122，注意从"一个变量等最低价"到"两个状态每天打分"的升级只多了一行方程。
四、完整推演表
121：
prices = [7, 1, 5, 3, 6, 4]（与动画默认一致）。
返回
5（第 1 天买、第 4 天卖）。复盘：
minPrice 只动了一次，
best 上了两次坡，
candidate 那列的最大值就是答案 —— 一列手算就能看穿整个算法。
122：
prices = [7, 1, 5, 3, 6, 4]，差值序列
-6, +4, -2, +3, -2。
返回
cash = 7。三件事同时成立：
greedy 列与
cash 列逐帧相等；
cash ≥ hold 恒成立（票没变现不更赚）；
hold 在第 1、3、5 天由"低位补仓"刷新 —— 下坡天 DP 也没闲着，它在
换更便宜的持仓成本。
五、追问连跳：309 / 714 / 123 / 188 —— 同一台机器改方程
股票系列的全部追问都长在同一张状态机图上，改的只是转移方程：
- LC 714 含手续费：卖出要交钱 —— 只改一行：
cash = max(cash, hold + price - fee)。贪心侧同样好办：吃正差时扣一次费（diff > fee 才吃）。手续费在买时扣还是卖时扣都行，只许扣一次。
- LC 309 含冷冻期：卖出后第二天不能买。给"刚卖"单独开一个状态
rest，三状态互相转移：hold = max(hold, rest - price)（只有冷冻结束才许买）、rest = hold + price（今天卖进冷冻）、cash = max(cash, rest)（冷冻自然到期）。状态从 2 个变 3 个，机器照跑。
- LC 123 最多两笔：把
cash/hold 按"已用笔数"复制 —— buy1, sell1, buy2, sell2 四个变量按依赖顺序各跑一遍 max：buy1 = max(buy1, -p)、sell1 = max(sell1, buy1 + p)、buy2 = max(buy2, sell1 - p)、sell2 = max(sell2, buy2 + p)。
- LC 188 最多 k 笔：再推广 ——
k 层 buy/sell 数组，O(nk)；当 k ≥ n/2 时交易数根本用不完，退化回 122 的贪心 —— 这一句是 188 的全部陷阱。
通用形态是教科书式的三维状态机
f[i][k][0|1]（第
i 天、至多
k 笔、持不持股）：121 是
k=1、122 是
k=+∞、123 是
k=2、188 是任意
k、309/714 是在转移上挂副作用。面试被连跳时，先画出 cash/hold 两个圈，再当场改箭头 —— 这比背四份代码值钱得多。
六、Java 版
class Solution {
// LC 121：一次买卖 —— 与推演表逐帧一致
public int maxProfit(int[] prices) {
int minPrice = prices[0], best = 0;
for (int i = 1; i < prices.length; i++) {
best = Math.max(best, prices[i] - minPrice); // 先卖一把
minPrice = Math.min(minPrice, prices[i]); // 再记最低价
}
return best;
}
}
class Solution {
// LC 122：无限次 —— cash/hold 状态机（贪心一行也满分，但要会讲等价）
public int maxProfit(int[] prices) {
int cash = 0, hold = -prices[0];
for (int i = 1; i < prices.length; i++) {
cash = Math.max(cash, hold + prices[i]);
hold = Math.max(hold, cash - prices[i]); // 用更新后的 cash 亦可：同日先卖后买 = 继续持有
}
return cash; // 终态必须空仓
}
}
class Solution {
// LC 309：冷冻期 —— 三状态
public int maxProfit(int[] prices) {
int cash = 0, hold = -prices[0], rest = 0; // rest：今天刚卖完
for (int i = 1; i < prices.length; i++) {
int prevCash = cash, prevHold = hold, prevRest = rest;
cash = Math.max(prevCash, prevRest); // 冷冻到期归空仓
hold = Math.max(prevHold, prevCash - prices[i]); // 只有空仓（非冷冻）能买
rest = prevHold + prices[i]; // 今天卖，进冷冻
}
return Math.max(cash, rest); // 终态不能持股
}
}
class Solution {
// LC 123：最多两笔 —— 四变量按依赖顺序更新
public int maxProfit(int[] prices) {
int buy1 = -prices[0], sell1 = 0, buy2 = -prices[0], sell2 = 0;
for (int p : prices) {
buy1 = Math.max(buy1, -p);
sell1 = Math.max(sell1, buy1 + p);
buy2 = Math.max(buy2, sell1 - p);
sell2 = Math.max(sell2, buy2 + p);
}
return sell2;
}
}
714 只需在 122 的卖支上减
fee：
cash = Math.max(cash, hold + prices[i] - fee);。
七、边界情况
- 只有一天：121/122 都返回 0 —— 没有"明天"可卖；
- 全程下跌（
[7,6,4,3,1]）：121 的 candidate 恒负、best 停在 0；122 的正差和为空，答案 0 —— "不交易"永远是合法策略；
- 价格全相等：差值全 0，
take 判据 diff > 0 不成立，答案 0；
- 单调上坡（
[1,2,3,4,5]）：121 直接返回 4；122 贪心逐日吃 +1 共 4，DP 侧 hold 全程 -1 不换手 —— 频繁买卖与连续持有利润相同，这正是贪心正确性的缩影；
- 121 的时序陷阱样本
[2,4,1]：全期最大差 4 - 1 = 3 是非法答案（低点在 4 之后），真实答案 2 —— 记住 121 是"顺序最大差"，不是"极差"；
- 188 的大 k：
k ≥ n/2 时按 122 处理，否则 O(nk) 白算一堆用不上的层。
八、复杂度
股票系列的空间优化全是同一招：转移只依赖"昨天"，滚动掉时间维就剩下几个
int。
九、常见坑
- 把 121 做成"最大减最小"：忽略时序。
[2,4,1] 的极差 3 非法，答案是 2 —— minPrice 必须边走边记，卖只能发生在未来。
- 忘了可以不交易：全程下跌时答案是 0 而不是最小负差。
best 初始化 0（不是 -∞）就是这条题意的落点。
- 122 贪心忘了
max(0, diff)：把差值直接累加等于"跌也吃"，[7,1,5] 会算成 -2。下坡的正确动作是空仓路过。
- DP 的
hold 初始化成 0：等于凭空一股"白送的成本"，或者干脆说允许了做空。建仓必须付钱：hold = -prices[0]。
- 终态取
hold：持股未变现不是利润。答案永远在 cash（309 里是 max(cash, rest)）。
- 309 忘了"卖后禁买"：只用两状态跑 122 的方程，冷冻期形同虚设 —— 必须给"刚卖"开第三个状态。
- 714 买卖两头各扣一次 fee：一笔交易只有一张账单，扣两次利润凭空少一截。
- 123 四变量乱序更新：
sell2 依赖 buy2、buy2 依赖 sell1 —— 顺序反了等于允许"第二笔买在第二笔卖之后"。按 buy1 → sell1 → buy2 → sell2 的依赖链走（同日买卖净额为零，链式更新恰好合法）。
十、面试怎么答
121 的三段话：① 换提问方式 —— 逐天问"今天卖最赚多少"，买入日必然是
截至昨天的最低价，于是 O(n²) 对枚举压成
minPrice/best 两个单调变量；② 全程下跌时 best 停在 0，"不买"是合法策略；③ 它是"顺序最大差"不是极差 ——
[2,4,1] 一口就能试出你有没有真懂。
122 的三段话：① 贪心：吃下所有正差，相邻正差可无缝拼接、连续上坡拆不拆利润相同，
O(n) 一行；② 状态机：
cash = max(不动, hold + p)、
hold = max(不动, cash - p)，终态取 cash；③ 加分项：现场说明
贪心 ≡ 状态机（动画逐帧
greedy === cash），DP 是贪心的证明。
被连跳追问时不要换题、要
改方程：714 在卖支减
fee；309 加
rest 状态、买只能从冷冻出来；123 把两状态按笔数复制成四变量；188 推广到 k 层、且
k ≥ n/2 退化回 122。一句话收尾："股票系列只有一道题 ——
f[i][k][0|1] 的状态机，其余都是参数。"
结语
121 教你
等：历史最低价是个耐心变量，它的全部意义是被未来的高价兑现；122 教你
舍：下坡不持仓、上坡不嫌碎，正差吃干净利润自然来。再往追问链上走，冷冻期、手续费、限笔数改的都是同两行转移方程 —— 状态机立得住，题目只是换皮。
下一篇见。