LeetCode 714. 买卖股票的最佳时机含手续费

2026-04-01 HGNULB 约 10 分钟

文章信息 9 个分类 3 个标签

分类

LeetCode CodeTop 中等未解决 5-10 字节跳动快手腾讯 LeetCode 75

题目描述

✅ 714. 买卖股票的最佳时机含手续费

题意分析

给一个按天排列的价格数组和一个固定的手续费，要求在允许无限次买卖的前提下求最大利润。每完成一笔完整交易（买入再卖出）要付一次手续费，最后手里不能留着股票。

「不限交易次数」这一条去掉了「最多买卖几次」这类计数维度，说明状态里不需要记录已经交易了多少笔。

「同一时间最多持有一股」是个强约束：它把「手里有多少股」压缩成了一个布尔值，任何一天收盘时的处境只有两种——空仓或满仓。这直接决定了需要跟踪的信息量极小。

手续费的存在改变了问题的性质。没有手续费时任何一段上涨都值得吃下，有了手续费之后，涨幅小于 fee 的波动做一次反而亏钱，所以必须能自动判断「这段涨幅值不值得付一次过路费」，以及「多段连续小涨要不要合并成一笔大交易来只付一次费用」。

数据规模上，价格数组长度可以到 $5 \times 10^4$，价格和手续费都不超过 $5 \times 10^4$，乘起来远在 int 范围内，不用担心溢出；但也说明只能接受线性或接近线性的做法，枚举所有买卖点组合的指数级方案不可行。

边界要注意：数组长度可能为 1，此时一天之内无法完成买卖，答案是 0；手续费可能为 0，退化成不限次数免费交易；也可能大到吃掉所有价差，此时最优解是一次都不交易，答案同样是 0，绝不会是负数。

解法：持有/不持有状态 DP

核心思路

暴力做法是枚举所有的买卖点组合：对每一天决定买、卖还是不动，递归下去取最大值。每天两三种选择，规模是指数级，在 $5 \times 10^4$ 天面前毫无希望。

瓶颈在于枚举把「之前具体在哪几天交易过」全部记了下来，而这些历史细节对未来的决策毫无用处。从今天往后能赚多少，只取决于一件事：今天收盘时手里有没有股票。之前是通过三笔小交易攒到现在的钱，还是一笔大交易攒到的，对后续没有任何区别。

这个观察把状态压到了两个。定义 cash 为「截至今天收盘、手上不持股时能拥有的最大现金」，hold 为「截至今天收盘、手上正持有一股时能拥有的最大现金」。注意 hold 是一个已经扣掉买入成本的净值，通常为负，它不是「利润」而是「现金余额」；只有把它当成余额来理解，后面的转移式才不需要任何特判。

转移只有四条来源。今天收盘空仓，要么昨天就空仓且今天什么都没做，要么昨天满仓且今天卖出，卖出收进 price 同时付掉 fee，于是 cash = max(cash, hold + price - fee)。今天收盘满仓，要么昨天就满仓且今天没动，要么昨天空仓且今天花 price 买入，于是 hold = max(hold, cash - price)。

手续费放在卖出侧扣是关键的建模选择。买入时不扣、卖出时扣一次，正好对应「一笔完整交易付一次费」；而且这样一来，cash - price 这个买入式里不含 fee，可以在同一笔持仓上反复不合算的卖出被自动淘汰——max 会自己判断「这次卖出扣完 fee 后是否还比不卖更优」，涨幅小于 fee 的波动会被自然地跳过，多段连续上涨也会被自然地合并成一笔。不需要任何显式的贪心判断。

初始条件由不变量倒推：第 0 天收盘空仓意味着没做任何交易，cash = 0；第 0 天收盘满仓只能是当天买入，hold = -prices[0]。答案是最后一天的 cash，因为手里攥着股票时那部分钱还没变现，一定不优于卖掉。

解题步骤

初始化 cash = 0、hold = -prices[0]，代表第 0 天收盘时的两种处境。hold 必须是负的买入成本而不是 0：0 会被误解成「白拿到一股」，让后面每一次卖出都凭空多赚一份 prices[0]。

从下标 1 开始遍历。下标 0 已经被初始化吃掉了，再遍历一次虽然不会改变数值——同一天按原价买卖的净收益不可能为正——但会让状态含义与「第 i 天收盘」错位。

每轮先把旧的 cash 存进 preCash。因为 cash 会在这一轮被就地更新，而下一行更新 hold 时按定义需要的是昨天的 cash。本题里即便直接用今天的 cash 答案也不会变——那等价于允许同一天先卖后买，而同一天卖了又买回来相当于什么都没做，还白付一次 fee，max 一定不会选它。快照的价值在于让代码严格对齐状态定义，换到有冷冻期或有交易次数限制的变体上，这一步就不再是可有可无的了。

更新 cash = max(cash, hold + prices[i] - fee)。右边的 hold 还是昨天的值，表示昨天满仓、今天以 prices[i] 卖出并付掉一次 fee；max 的另一侧是昨天空仓今天不动。这一步之后 cash 变成今天的值。

更新 hold = max(hold, preCash - prices[i])，用的是 preCash。含义是昨天空仓、今天以 prices[i] 买入。买入不扣 fee，费用统一在卖出侧结算。

返回 cash。不要在最后拿 max(cash, hold)：hold 是持仓状态的现金余额，把股票攥在手上不卖只会更差，而且题目要求最终不持股。

以 prices = [1, 3, 2, 8, 4, 9]、fee = 2 走一遍（答案 8）：初始 cash = 0、hold = -1。第 1 天价格 3：preCash = 0，卖出候选 -1 + 3 - 2 = 0，不优于 0，cash 仍为 0；买入候选 0 - 3 = -3，劣于 -1，hold 仍为 -1——这里正好体现了手续费的过滤作用，价差 2 刚好等于 fee，做这笔白忙一场。第 2 天价格 2：卖出候选 -1 + 2 - 2 = -1，cash 保持 0；买入候选 0 - 2 = -2，仍劣于 -1，hold 保持 -1，说明第 0 天以 1 买入依然是最划算的建仓点。第 3 天价格 8：卖出候选 -1 + 8 - 2 = 5，cash 更新为 5；买入候选用的是 preCash = 0，得 -8，hold 保持 -1。第 4 天价格 4：卖出候选 -1 + 4 - 2 = 1，劣于 5，cash 保持 5；买入候选 preCash - 4 = 5 - 4 = 1，优于 -1，hold 更新为 1——这一步就是「先落袋 5，再用其中一部分在低点 4 重新建仓」。第 5 天价格 9：卖出候选 1 + 9 - 2 = 8，cash 更新为 8；买入候选 5 - 9 = -4，劣于 1，hold 保持 1。返回 8，对应「1 买 8 卖赚 5，4 买 9 卖赚 3」两笔交易，中间价格 3、2 的小波动被 max 自动跳过。

代码实现

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int cash = 0;
        int hold = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            int preCash = cash;

            // cash 表示不持股，hold 表示持股，手续费在卖出时扣除。
            cash = Math.max(cash, hold + prices[i] - fee);
            hold = Math.max(hold, preCash - prices[i]);
        }
        return cash;
    }
}

func maxProfit(prices []int, fee int) int {
    cash := 0
    hold := -prices[0]
    for i := 1; i < len(prices); i++ {
        preCash := cash

        // cash 表示不持股，hold 表示持股，手续费在卖出时扣除。
        if hold+prices[i]-fee > cash {
            cash = hold + prices[i] - fee
        }
        if preCash-prices[i] > hold {
            hold = preCash - prices[i]
        }
    }
    return cash
}

复杂度分析

时间复杂度：$O(n)$。凭什么：价格数组只被从左到右扫描一遍，每天固定做两次比较和两次加减，没有任何嵌套循环或回溯，代价与 n 严格成正比。

空间复杂度：$O(1)$。凭什么：转移式只引用前一天的两个状态，所以二维的 dp[i][0..1] 可以被 cash、hold 两个标量加一个临时变量 preCash 完全替代，占用与 n 无关。

关键点总结

股票类问题的通用套路是「按持仓状态分层」：先问清楚一天收盘时手里可能处于哪几种处境，每种处境定义一个 dp 变量，再逐条列出处境之间的合法转移。本题是最基础的两层，加冷冻期变三层，加交易次数上限则再乘一个维度。

状态定义要写成「现金余额」而不是「利润」。余额允许为负、天然包含了买入成本，转移式写起来是纯粹的加减；写成利润就得在买入时额外记住成本价，反而多一个维度。

手续费扣在卖出侧还是买入侧都能得到正确答案，但必须二选一、只扣一次。扣在卖出侧的好处是初始值 hold = -prices[0] 不含 fee，含义最干净。

滚动更新时凡是同一轮里既被读又被写的变量，都要先快照。这条规则超出本题：只要 dp 从二维压到一维且转移引用同层的其他位置，就得考虑遍历方向或临时变量。

贪心解法和这套 dp 可以得到相同结果，但 DP 更容易证明：空仓、持仓穷尽了每天收盘的所有合法状态，每个状态又完整枚举了「今天不动」与「今天交易」两类来源，因此逐日取最大值不会漏掉最优方案。max 也会自动完成「小于 fee 的涨幅不值得做」和「连续上涨合并成一笔」，不必额外写判断。

面试视角：答题时先把两个状态的中文含义一字不差地说出来，再列四条转移，最后才写代码。面试官在这题上主要考「你能不能把状态定义讲清楚」，而不是考你能不能背出五行循环；状态含义含糊的候选人，一被追问「hold 为什么是负的」就会崩。

面试视角：高频追问是「和 122 有什么区别」「加了冷冻期怎么改」「限制最多两笔怎么改」。准备好一句话答案——122 是 fee = 0 的特例；冷冻期要把空仓拆成「今天刚卖」和「已休息」两态，买入只能从后者转移；限制笔数则在状态上再加一维交易次数。

易错点总结

错误写法：把 hold 初始化为 0。用例 prices = [1, 5]、fee = 0 → 第 1 天卖出候选算成 0 + 5 - 0 = 5，输出 5，正确答案是 4；hold = 0 等于白送一股，第 0 天的买入成本凭空消失。

错误写法：买入和卖出各扣一次手续费，把买入写成 hold = max(hold, preCash - prices[i] - fee) 且卖出仍减 fee。用例 prices = [1, 3, 2, 8, 4, 9]、fee = 2 → 输出 6，正确答案是 8；一笔完整交易只付一次过路费。

错误写法：转移里彻底忘了减 fee，写成 cash = max(cash, hold + prices[i])。用例 prices = [1, 3, 2, 8, 4, 9]、fee = 2 → 输出 13，那是 122 题（无手续费）的答案，正确答案是 8。

错误写法：决定把手续费改扣在买入侧，却只改了转移没改初始值——hold 仍初始化为 -prices[0]，转移写成 hold = max(hold, preCash - prices[i] - fee)、cash = max(cash, hold + prices[i])。用例 prices = [1, 3, 2, 8, 4, 9]、fee = 2 → 输出 10，因为第 0 天那次建仓白嫖了一次免费手续费，正确答案是 8。

错误写法：反过来把 hold 初始化为 -prices[0] - fee，却忘了卖出侧的 fee 要去掉。用例 prices = [1, 3, 2, 8, 4, 9]、fee = 2 → 首笔交易被扣了两次费，输出 6，正确答案是 8。

错误写法：照搬 121 题只能交易一次的模板，把买入写成 hold = max(hold, -prices[i])。用例 prices = [1, 3, 2, 8, 4, 9]、fee = 2 → 买入不再继承此前累积的现金，等价于全程只允许做一笔，输出 6，正确答案是 8。

错误写法：套用无手续费的贪心，把每一段相邻上涨都当作一笔交易并各减一次 fee。用例 prices = [1, 3, 2, 8, 4, 9]、fee = 2 → 三段涨幅 2、6、5 各减 2 得 0 + 4 + 3 = 7，正确答案是 8；1 买 8 卖本该合并成一笔只付一次费，逐段拆开反而多付了。

错误写法：认为一定要做一笔交易，直接返回「最大价差减去 fee」。用例 prices = [1, 3]、fee = 5 → 输出 -3，正确答案是 0；cash 的初始值 0 就是「一次都不交易」的兜底，手续费吃光价差时不做才是最优。

相似题目

题目	难度	考察点
121. 买卖股票的最佳时机	简单	只许交易一次，买入不能继承此前现金，`hold` 转移退化成 `max(hold, -price)`
122. 买卖股票的最佳时机 II	中等	本题令 `fee = 0` 的特例，因此逐段吃涨的贪心在那里成立、在这里不成立
123. 买卖股票的最佳时机 III	困难	交易次数被限制成两笔，状态从两个膨胀到四个，需按笔数分层
188. 买卖股票的最佳时机 IV	困难	把笔数上限参数化成 `k`，状态多出一维，还要处理 `k` 大于天数一半的退化
198. 打家劫舍	中等	同样是两状态滚动 DP，但约束来自相邻位置互斥而非持仓，可对照体会状态设计
309. 买卖股票的最佳时机含冷冻期	中等	空仓要拆成「今天刚卖」和「已休息」两态，买入只能从后者转移
剑指 Offer 63. 股票的最大利润	中等	与 121 同题，适合用来验证「一次交易」和「无限次交易」两套模板的差别