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

Categories:

题目描述
思路分析
1. 解法一：状态机动态规划（推荐）
相似题目

题目描述

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

思路分析

解法一：状态机动态规划（推荐）

核心思路：

冷冻期约束使得“不持有”要区分为“刚卖出”和“可买入”。

设三种状态：

hold：持有股票

sold：当天刚卖出（次日冷冻）

rest：不持有且可买入

状态转移：

hold = max(hold, rest - price)

sold = prevHold + price

rest = max(rest, prevSold)

复杂度分析：

时间复杂度：O(n)，其中 n 表示天数。

空间复杂度：O(1)，仅用常数状态变量。

class Solution {
    public int maxProfit(int[] prices) {
        int hold = -prices[0];
        int sold = 0;
        int rest = 0;

        for (int i = 1; i < prices.length; i++) {
            int prevHold = hold;
            int prevSold = sold;
            int prevRest = rest;

            hold = Math.max(prevHold, prevRest - prices[i]);
            sold = prevHold + prices[i];
            rest = Math.max(prevRest, prevSold);
        }

        return Math.max(sold, rest);
    }
}

func maxProfit(prices []int) int {
	hold := -prices[0]
	sold := 0
	rest := 0

	for i := 1; i < len(prices); i++ {
		prevHold, prevSold, prevRest := hold, sold, rest

		hold = max309(prevHold, prevRest-prices[i])
		sold = prevHold + prices[i]
		rest = max309(prevRest, prevSold)
	}

	return max309(sold, rest)
}

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

相似题目

题目	难度	考察点
121. 买卖股票的最佳时机	简单	动态规划、贪心
122. 买卖股票的最佳时机 II	中等	贪心
123. 买卖股票的最佳时机 III	困难	动态规划
188. 买卖股票的最佳时机 IV	困难	动态规划
714. 买卖股票的最佳时机含手续费	中等	动态规划、贪心
198. 打家劫舍	中等	动态规划
213. 打家劫舍 II	中等	动态规划
740. 删除并获得点数	中等	动态规划
256. 粉刷房子	中等	动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/32087705