LeetCode 309. 买卖股票的最佳时机含冷冻期

2026-03-27 HGNULB 约 6 分钟

文章信息 9 个分类 3 个标签

分类

题目描述

✅ 309. 买卖股票的最佳时机含冷冻期

题意分析

给一个按天排列的价格数组，允许无限次买卖，但每次卖出之后必须空一天才能再次买入，求能拿到的最大利润。

「不限交易次数」说明状态里不需要记录已经做了几笔；「同一时间最多持有一股」把仓位压成一个是非题。这两条合起来意味着需要跟踪的信息量本来很小。

真正的难点是冷冻期。它让「今天空仓」这一件事变得不再单一：昨天刚卖掉股票的空仓，和已经空仓好几天的空仓，明天的可选动作完全不同——前者明天不许买，后者明天随便买。也就是说，只知道「手里有没有股票」已经不足以决定未来，还得知道「是不是刚卖」。

换个角度看，冷冻期的约束是加在买入这个动作上的，而不是加在卖出上：卖出永远自由，被禁止的只是「卖出后紧接着的那次买入」。把限制挂在买入侧，是后面所有推导的出发点。

数据规模上价格数组长度可达 5000，价格不超过 1000，乘积远在 int 范围内不必担心溢出；但也说明枚举所有买卖点组合的指数级做法行不通。

边界要注意：数组长度可能为 1，一天之内无法完成任何交易，答案是 0；价格全程单调下跌时最优解是一次都不做，答案同样是 0，绝不会是负数。

解法：三状态股票 DP

核心思路

冷冻期只限制一件事：昨天卖出，今天不能买入。因此「空仓」必须拆成两种对下一天影响不同的状态：

hold：当天结束时持有股票的最大现金；

sold：当天刚卖出、处于冷冻期的最大现金；

rest：当天结束时空仓且不在冷冻期，下一天可以买入的最大现金。

设 price 为当天价格，所有右侧状态都取自前一天，则转移为：

hold = max(preHold, preRest - price)：继续持有，或从可买入的 rest 买入；不能从 preSold 买入，这一限制就是冷冻期。

sold = preHold + price：只有昨天持股、今天卖出这一种来源。

rest = max(preRest, preSold)：继续休息，或让昨天卖出的人度过一天冷冻期。

初始时 hold = -prices[0]、rest = 0，而 sold 不可达，设为足够小的负数。最终必须空仓才算完整利润，因此答案是 max(sold, rest)。

正确性依据：三个状态覆盖每天结束时的全部合法处境且互不重叠；每条转移又枚举了到达该状态的所有合法前驱。若前一天各状态已经最优，取这些前驱的最大值后，当天各状态也最优，归纳可得最终答案最优。

解题步骤

用第 0 天初始化三个状态：买入得到 hold，不操作得到 rest，sold 标记为不可达。

从第 1 天开始遍历。每轮先保存 preHold、preSold、preRest，保证三条转移只读取前一天，而不是读到本轮刚更新的值。

按 hold → sold → rest 的公式计算当天状态。特别检查 hold 的买入来源只能是 preRest。

遍历结束后返回两种空仓状态的较大值。

以 [1, 2, 3, 0, 2] 为例，三元组按 (hold, sold, rest) 记录：

(-1, -∞, 0) → (-1, 1, 0) → (-1, 2, 1) → (1, -1, 2) → (1, 3, 2)。

第 3 天价格为 0 时，只能使用第 2 天的 rest = 1 再买入；这笔 1 来自更早卖出且已经完成冷冻的收益。最终答案为 3。

代码实现

class Solution {
    public int maxProfit(int[] prices) {
        int hold = -prices[0];
        int sold = Integer.MIN_VALUE / 2;
        int rest = 0;
        for (int i = 1; i < prices.length; i++) {
            int preHold = hold;
            int preSold = sold;
            int preRest = rest;

            hold = Math.max(preHold, preRest - prices[i]);
            sold = preHold + prices[i];
            rest = Math.max(preRest, preSold);
        }
        return Math.max(sold, rest);
    }
}

func maxProfit(prices []int) int {
    hold := -prices[0]
    sold := -1_000_000_000
    rest := 0
    for i := 1; i < len(prices); i++ {
        preHold := hold
        preSold := sold
        preRest := rest

        hold = maxStock(preHold, preRest-prices[i])
        sold = preHold + prices[i]
        rest = maxStock(preRest, preSold)
    }
    return maxStock(sold, rest)
}

func maxStock(a int, b int) int {
    if a > b {
        return a
    }
    return b
}

复杂度分析

时间复杂度：$O(n)$，每个价格只处理一次，每天只做常数次状态转移。

空间复杂度：$O(1)$，状态只依赖前一天，用三个状态和三个快照变量即可。

关键点总结

是否需要拆状态，看它们对未来动作的限制是否不同；sold 和 rest 都空仓，但第二天能否买入不同，所以必须分开。

冷冻期没有额外计数器，它完整地体现在 hold 只能从 preRest 买入。

sold 表示「今天刚卖」，来源唯一，所以转移不需要与旧 sold 取最大值。

空间压缩后要先快照全部旧状态，否则一次循环内会发生本不允许的连续操作。

若冷冻期改为 k 天，需要保存更早的可买入状态；本题只有一天，三个状态足够。

易错点总结

买入从 preSold 转移：等于允许卖出后的第二天立即买入；[1, 2, 3, 0, 2] 会错误得到 4，正确答案是 3。

原地覆盖旧状态：若 sold 读取本轮刚更新的 hold，或 rest 读取本轮 sold，就把多天动作压进同一天。必须先整体快照。

遗漏 preSold → rest：卖出收益无法离开冷冻状态，算法实际上只能完成一笔交易。

把 hold 初始化为 0：相当于免费得到一股；正确初值是 -prices[0]。

照搬 122 题累计所有正差值：该贪心默认卖出后可以立即再次买入，不满足本题约束。

相似题目

题目	难度	考察点
121. 买卖股票的最佳时机	简单	只许交易一次，买入不继承此前现金，`hold` 转移退化成 `max(hold, -price)`
122. 买卖股票的最佳时机 II	中等	去掉冷冻期后空仓不必拆分，逐段吃涨的贪心在那里成立、在本题不成立
123. 买卖股票的最佳时机 III	困难	限制两笔交易，状态按笔数分层而非按冷冻状态分层，是另一个方向的扩维
188. 买卖股票的最佳时机 IV	困难	笔数上限参数化成 `k`，还要处理 `k` 超过天数一半时退化为无限次的情况
198. 打家劫舍	中等	同样是「选了这个就不能选相邻的」，可对照体会隔一位转移与冷冻期的同构之处
714. 买卖股票的最佳时机含手续费	中等	附加规则落在卖出侧扣费而非买入侧限流，因此两个状态就够，不必拆分空仓
剑指 Offer 63. 股票的最大利润	中等	与 121 同题，适合用来对照「一次交易」和「无限次加冷冻期」两套状态设计