TNotes.leetcode

Appearance

⏰0309. 买卖股票的最佳时机含冷冻期【中等】

0309. 买卖股票的最佳时机含冷冻期【中等】 ​

1. 📝 题目描述 ​

给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格。​

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

  • 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1：

txt
输入: prices = [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

示例 2：

txt
输入: prices = [1]
输出: 0

提示：

  • 1 <= prices.length <= 5000
  • 0 <= prices[i] <= 1000

2. 🎯 s.1 - 状态机 DP ​

c
int maxProfit(int* prices, int pricesSize) {
    if (pricesSize == 0) return 0;
    int hold = -prices[0], sold = 0, rest = 0;
    for (int i = 1; i < pricesSize; i++) {
        int prevSold = sold;
        sold = hold + prices[i];
        hold = hold > rest - prices[i] ? hold : rest - prices[i];
        rest = rest > prevSold ? rest : prevSold;
    }
    return sold > rest ? sold : rest;
}
js
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  const n = prices.length
  if (n === 0) return 0
  let hold = -prices[0],
    sold = 0,
    rest = 0
  for (let i = 1; i < n; i++) {
    const prevSold = sold
    sold = hold + prices[i]
    hold = Math.max(hold, rest - prices[i])
    rest = Math.max(rest, prevSold)
  }
  return Math.max(sold, rest)
}
py
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        hold, sold, rest = -prices[0], 0, 0
        for i in range(1, len(prices)):
            prev_sold = sold
            sold = hold + prices[i]
            hold = max(hold, rest - prices[i])
            rest = max(rest, prev_sold)
        return max(sold, rest)
  • 时间复杂度：O(n)，其中 n 是价格数组长度
  • 空间复杂度：O(1)，只使用常数额外空间

算法思路：

  • 三种状态：持有股票（hold）、刚卖出（sold）、冷冻/空闲（rest）
  • hold = max(hold, rest - price)，sold = hold + price，rest = max(rest, prevSold)
  • 卖出后下一天必须冷冻，所以只能从 rest 状态买入