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

约 5 分钟
文章信息 9 个分类 2 个标签
分类
LeetCode CodeTop 中等 已解决 5-10 腾讯 美团 小红书 快手
标签
数组 动态规划

题目描述

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

image-20260928235654048

题意分析

可以多次买卖股票，但同一时间最多持有一股，卖出后的下一天不能买入。空仓时还要区分今天是否刚卖出，因为这决定了明天有没有买入资格。

解法：三状态股票 DP

核心思路

[!blue]

三个状态都表示对应日末情况能得到的最大累计现金：hold 表示持有一股，已扣除买入成本；sold 表示今天刚卖出，明天需要冷冻；rest 表示当前空仓且今天没有卖出，明天可以买入。rest 也包含今天刚度过冷冻期的情况。

设今天价格为 price，按今天的最后一个动作列出转移：

  • hold = max(旧 hold, 旧 rest - price)：继续持股，或者从昨天允许今天买入的空仓状态买入。
  • sold = 旧 hold + price：今天刚卖出，只能来自昨天持股。旧 sold 不能直接保留到这个状态，否则就不再表示“今天刚卖”。
  • rest = max(旧 rest, 旧 sold)：昨天已经休息且今天继续休息，或者昨天刚卖出、今天完整度过冷冻期。

卖出后的下一天只能从 sold 进入 rest，再下一天才能从 rest 买入进入 hold，所以冷冻期已包含在转移关系中。这三种情况覆盖全部日末状态；同一状态对未来操作的限制相同，保留现金最多的方案即可。

第一天可选择买入或不操作，因此 hold = -prices[0]、rest = 0；sold 初始化为表示不可达的负无穷，代码用足够小的负数表示。最后返回 max(sold, rest)，两者都是已完成交易的空仓收益；只有一天时，答案自然为 $0$。

解题步骤

  1. 用第 0 天初始化三个状态：买入得到 hold，不操作得到 rest，sold 标记为不可达。
  2. 从第 1 天开始遍历。每轮先保存 preHold、preSold、preRest，保证三条转移只读取前一天，而不是读到本轮刚更新的值。
  3. 用三个快照计算当天的 hold、sold、rest。其中买入来源只能是 preRest，preSold 必须先进入休息状态。
  4. 遍历结束后返回两种空仓状态的较大值。

代码实现

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)$，状态只依赖前一天，用三个状态和三个快照变量即可。

关键点总结

[!green]

  • 是否需要拆状态，看它们对未来动作的限制是否不同；sold 今天刚卖而明天不可买，rest 明天可买，包括今天完成冷冻的情况，所以必须分开。
  • 冷冻期没有额外计数器，它完整地体现在 hold 只能从 preRest 买入。
  • sold 表示「今天刚卖」，来源唯一，所以转移不需要与旧 sold 取最大值。
  • 空间压缩后要先快照全部旧状态，否则一次循环内会发生本不允许的连续操作。

易错点总结

[!yellow]

  • 买入从 preSold 转移：等于允许卖出后的次日立即买入，跳过了必须休息的一天。
  • 混用新旧状态：若 rest 读取本轮刚更新的 sold，当天刚卖出的收益就会变成明天可买，冷冻期被提前跳过。先整体快照可保证每条转移都来自昨天。
  • 遗漏 preSold → rest：卖出收益无法离开冷冻状态，算法实际上只能完成一笔交易。
  • 把 hold 初始化为 0：相当于免费得到一股；正确初值是 -prices[0]。
  • 照搬 122 题累计所有正差值：该贪心默认卖出后可以立即再次买入，不满足本题约束。

相似题目

题目 难度 关联与区别
122. 买卖股票的最佳时机 II 中等 交易次数都不受限，但本题卖出后不能次日买入，需要额外冷冻状态。
714. 买卖股票的最佳时机含手续费 中等 同样在基础持有/空仓状态中增加约束，原题收手续费，本题限制交易时机。
121. 买卖股票的最佳时机 简单 以持有状态和交易次数描述每天的最优收益；本题卖出后增加冷冻限制，该题只允许一次买卖。
123. 买卖股票的最佳时机 III 困难 以持有状态和交易次数描述每天的最优收益；本题卖出后增加冷冻限制，该题最多完成两笔交易。
188. 买卖股票的最佳时机 IV 困难 以持有状态和交易次数描述每天的最优收益；本题卖出后增加冷冻限制，该题推广到 k 笔交易。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/32087705
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！