Medium

题目描述

给定一个整数数组 prices，其中 prices[i] 表示第 i 天的股票价格（以美元计），以及一个整数 k。

你最多可以进行 k 次交易，每次交易可以是以下两种类型之一：

  • 正常交易：在第 i 天买入，然后在之后的第 j 天卖出（i < j）。利润为 prices[j] - prices[i]。
  • 卖空交易：在第 i 天卖出，然后在之后的第 j 天买回（i < j）。利润为 prices[i] - prices[j]。

注意，你必须在开始另一笔交易之前完成当前交易。此外，你不能在进行前一笔交易的买入或卖出的同一天进行卖出或买入。

返回通过最多 k 次交易可以获得的最大总利润。

示例 1：

输入：prices = [1,7,9,8,2], k = 2
输出：14
解释：
我们可以通过 2 次交易获得 $14 的利润：
- 正常交易：第 0 天以 $1 买入股票，然后第 2 天以 $9 卖出。
- 卖空交易：第 3 天以 $8 卖出股票，然后第 4 天以 $2 买回。

示例 2：

输入：prices = [12,16,19,19,8,1,19,13,9], k = 3
输出：36
解释：
我们可以通过 3 次交易获得 $36 的利润：
- 正常交易：第 0 天以 $12 买入，第 2 天以 $19 卖出。
- 卖空交易：第 3 天以 $19 卖出，第 4 天以 $8 买回。
- 正常交易：第 5 天以 $1 买入，第 6 天以 $19 卖出。

约束条件：

  • 2 <= prices.length <= 10³
  • 1 <= prices[i] <= 10⁹
  • 1 <= k <= prices.length / 2

解题思路

这道题是经典的股票买卖问题的变种，增加了卖空交易的概念。我们需要使用动态规划来解决。

核心思路：

我们需要维护四个状态：

  • idx：当前处理到的天数
  • transactionsDone：已完成的交易次数
  • transactionType：交易类型（0表示正常交易，1表示卖空交易）
  • isTransactionRunning：是否有正在进行的交易（0表示无交易，1表示有交易）

状态转移：

对于每一天，我们有以下选择：

  1. 什么都不做
  2. 开始一笔新交易（买入或卖出）
  3. 完成当前交易（卖出或买回）

关键观察：由于我们可以进行正常交易和卖空交易，实际上我们可以在任何相邻的价格差中获利。如果价格上涨，我们进行正常交易；如果价格下跌，我们进行卖空交易。

优化思路：

由于交易次数限制和交易类型的灵活性，我们可以使用记忆化递归来实现动态规划。但更简单的方法是认识到：在最多k次交易的限制下，我们应该选择最大的k个价格差进行交易。

因此，我们可以计算所有相邻天数的价格差，取绝对值，然后选择最大的k个进行交易。

代码实现

class Solution {
public:
    long long maximumProfit(vector<int>& prices, int k) {
        int n = prices.size();
        vector<long long> diffs;
        
        // 计算所有相邻价格差的绝对值
        for (int i = 1; i < n; i++) {
            diffs.push_back(abs((long long)prices[i] - prices[i-1]));
        }
        
        // 排序并取最大的k个差值
        sort(diffs.rbegin(), diffs.rend());
        
        long long result = 0;
        for (int i = 0; i < min(k, (int)diffs.size()); i++) {
            result += diffs[i];
        }
        
        return result;
    }
};

class Solution:
    def maximumProfit(self, prices: List[int], k: int) -> int:
        n = len(prices)
        diffs = []
        
        # 计算所有相邻价格差的绝对值
        for i in range(1, n):
            diffs.append(abs(prices[i] - prices[i-1]))
        
        # 排序并取最大的k个差值
        diffs.sort(reverse=True)
        
        result = 0
        for i in range(min(k, len(diffs))):
            result += diffs[i]
        
        return result

public class Solution {
    public long MaximumProfit(int[] prices, int k) {
        int n = prices.Length;
        List<long> diffs = new List<long>();
        
        // 计算所有相邻价格差的绝对值
        for (int i = 1; i < n; i++) {
            diffs.Add(Math.Abs((long)prices[i] - prices[i-1]));
        }
        
        // 排序并取最大的k个差值
        diffs.Sort((a, b) => b.CompareTo(a));
        
        long result = 0;
        for (int i = 0; i < Math.Min(k, diffs.Count); i++) {
            result += diffs[i];
        }
        
        return result;
    }
}

var maximumProfit = function(prices, k) {
    const n = prices.length;
    const diffs = [];
    
    // 计算所有相邻价格差的绝对值
    for (let i = 1; i < n; i++) {
        diffs.push(Math.abs(prices[i] - prices[i-1]));
    }
    
    // 排序并取最大的k个差值
    diffs.sort((a, b) => b - a);
    
    let result = 0;
    for (let i = 0; i < Math.min(k, diffs.length); i++) {
        result += diffs[i];
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

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

其中 n 是 prices 数组的长度。时间复杂度主要来自于排序操作，空间复杂度来自于存储价格差值的数组。

相关题目