Medium

题目描述

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

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

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

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

示例 1:

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

示例 2:

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

提示:

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

解题思路

这道题是股票买卖系列的经典题目，关键在于处理冷冻期约束。我们可以用动态规划来解决。

状态定义：每一天都有三种状态：

  1. hold[i]：第i天持有股票的最大收益
  2. sold[i]：第i天刚卖出股票的最大收益（处于冷冻期）
  3. rest[i]：第i天休息的最大收益（可以买入）

状态转移：

  • hold[i] = max(hold[i-1], rest[i-1] - prices[i])：要么继续持有，要么从休息状态买入
  • sold[i] = hold[i-1] + prices[i]：从持有状态卖出
  • rest[i] = max(rest[i-1], sold[i-1])：要么继续休息，要么从冷冻期恢复

由于每个状态只依赖前一天的状态，我们可以用三个变量来优化空间复杂度。最终答案是 max(sold, rest)，因为最后一天不应该持有股票。

代码实现

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n <= 1) return 0;
        
        int hold = -prices[0];  // 持有股票
        int sold = 0;           // 刚卖出（冷冻期）
        int rest = 0;           // 休息状态
        
        for (int i = 1; i < n; i++) {
            int prevHold = hold;
            int prevSold = sold;
            int prevRest = rest;
            
            hold = max(prevHold, prevRest - prices[i]);
            sold = prevHold + prices[i];
            rest = max(prevRest, prevSold);
        }
        
        return max(sold, rest);
    }
};

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        if n <= 1:
            return 0
        
        hold = -prices[0]  # 持有股票
        sold = 0           # 刚卖出（冷冻期）
        rest = 0           # 休息状态
        
        for i in range(1, n):
            prev_hold = hold
            prev_sold = sold
            prev_rest = rest
            
            hold = max(prev_hold, prev_rest - prices[i])
            sold = prev_hold + prices[i]
            rest = max(prev_rest, prev_sold)
        
        return max(sold, rest)

public class Solution {
    public int MaxProfit(int[] prices) {
        int n = prices.Length;
        if (n <= 1) return 0;
        
        int hold = -prices[0];  // 持有股票
        int sold = 0;           // 刚卖出（冷冻期）
        int rest = 0;           // 休息状态
        
        for (int i = 1; i < n; 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);
    }
}

var maxProfit = function(prices) {
    const n = prices.length;
    if (n <= 1) return 0;
    
    let hold = -prices[0];  // 持有股票
    let sold = 0;           // 刚卖出（冷冻期）
    let rest = 0;           // 休息状态
    
    for (let i = 1; i < n; i++) {
        const prevHold = hold;
        const prevSold = sold;
        const prevRest = rest;
        
        hold = Math.max(prevHold, prevRest - prices[i]);
        sold = prevHold + prices[i];
        rest = Math.max(prevRest, prevSold);
    }
    
    return Math.max(sold, rest);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(1)

相关题目