Medium

题目描述

给定一个整数数组 prices，其中 prices[i] 表示第 i 天的股票价格；整数 fee 代表了交易手续费。

你可以完成任意次数的交易，但是你每笔交易都需要付手续费。如果你已经购买了一只股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意： 这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为此支付一次手续费。

示例 1：

输入：prices = [1,3,2,8,4,9], fee = 2
输出：8
解释：能够达到的最大利润:  
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8

示例 2：

输入：prices = [1,3,7,5,10,3], fee = 3
输出：6

提示：

  • 1 <= prices.length <= 5 * 10^4
  • 1 <= prices[i] < 5 * 10^4
  • 0 <= fee < 5 * 10^4

解题思路

这是一道经典的股票买卖动态规划题目。核心思想是维护两种状态：持有股票和不持有股票时的最大利润。

解法分析：

  1. 动态规划解法：定义状态 hold[i] 表示第i天持有股票的最大利润，sold[i] 表示第i天不持有股票的最大利润。状态转移方程为：

    • hold[i] = max(hold[i-1], sold[i-1] - prices[i])
    • sold[i] = max(sold[i-1], hold[i-1] + prices[i] - fee)

  2. 贪心解法：维护一个有效购买价格，当当前价格减去手续费大于有效购买价格时卖出，并更新购买价格。

  3. 空间优化：由于状态转移只依赖前一天，可以用两个变量代替数组。

推荐解法： 使用空间优化的动态规划，时间复杂度O(n)，空间复杂度O(1)，思路清晰且易于理解。

关键点是理解手续费只在卖出时支付，以及正确处理状态转移中的买卖逻辑。

代码实现

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int hold = -prices[0]; // 持有股票的最大利润
        int sold = 0;          // 不持有股票的最大利润
        
        for (int i = 1; i < prices.size(); i++) {
            int newHold = max(hold, sold - prices[i]);
            int newSold = max(sold, hold + prices[i] - fee);
            hold = newHold;
            sold = newSold;
        }
        
        return sold;
    }
};

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        hold = -prices[0]  # 持有股票的最大利润
        sold = 0           # 不持有股票的最大利润
        
        for i in range(1, len(prices)):
            hold, sold = max(hold, sold - prices[i]), max(sold, hold + prices[i] - fee)
        
        return sold

public class Solution {
    public int MaxProfit(int[] prices, int fee) {
        int hold = -prices[0]; // 持有股票的最大利润
        int sold = 0;          // 不持有股票的最大利润
        
        for (int i = 1; i < prices.Length; i++) {
            int newHold = Math.Max(hold, sold - prices[i]);
            int newSold = Math.Max(sold, hold + prices[i] - fee);
            hold = newHold;
            sold = newSold;
        }
        
        return sold;
    }
}

var maxProfit = function(prices, fee) {
    let hold = -prices[0]; // 持有股票的最大利润
    let sold = 0;          // 不持有股票的最大利润
    
    for (let i = 1; i < prices.length; i++) {
        let newHold = Math.max(hold, sold - prices[i]);
        let newSold = Math.max(sold, hold + prices[i] - fee);
        hold = newHold;
        sold = newSold;
    }
    
    return sold;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)需要遍历一次价格数组
空间复杂度O(1)只使用常数个变量存储状态

相关题目