LeetCode 188. 买卖股票的最佳时机 IV

2025-10-22 HGNULB 约 6 分钟

文章信息 10 个分类 · 2 个标签

分类

LeetCode CodeTop 困难 未解决 10-20 面试经典 150 题 腾讯 字节 小米 百度

标签

数组 动态规划

题目描述

✅ 188. 买卖股票的最佳时机 IV

题意分析

一笔交易由一次买入和之后的一次卖出组成，最多完成 k 笔，而且必须卖掉手中的股票才能再次买入。目标是全部交易结束后的最大利润；允许少做交易，价格一直下降时也可以一笔都不做。

决定今天能否买卖，需要知道两个信息：目前是否持股，以及还有多少交易额度。因此按交易次数分别维护持股和空仓状态。

解法：交易次数状态动态规划

核心思路

[!blue]

对每个 t = 1...k，维护处理完当天后的两种最优现金余额：

• buy[t]：累计买入不超过 t 次，并且当前持有一股。手中这股尚未卖出，所以余额已经扣除了它的买入价。
• sell[t]：已完成不超过 t 笔交易，并且当前没有股票。sell[0] 始终为 0，表示没有交易额度，只能空仓。

设今天价格为 p。持股可以由昨天继续持有，也可以从最多完成 t-1 笔交易的空仓状态花 p 买入，因此 buy[t] = max(buy[t], sell[t-1] - p)。空仓可以由昨天继续空仓，也可以把持有的股票卖出，因此 sell[t] = max(sell[t], buy[t] + p)。两种转移都保留旧状态，表示今天不操作。

首日令所有 sell[t] = 0、buy[t] = -prices[0]。这里是“最多”而不是“恰好”交易 t 次，所以即使 t > 1，只买一次或完全不交易仍是合法状态，不需要强行凑满次数。

代码按 t 从小到大原地更新，可能读到当天刚更新的状态，相当于允许同一天先卖再买或先买再卖。这些动作都使用同一个价格：同日买卖可以删除，同日卖出再买入可以合并为继续持有。消去后收益不变、交易次数只会减少，因此不会虚增“最多 k 笔”的答案。

还有一个可提前处理的情况：k >= n / 2。把同日卖出再买入合并后，每笔有效交易至少占两个不同的交易日，因此这个额度已能容纳最优方案。此时累加所有正的相邻价格差即可：任何一段持有收益都等于该段每日差值之和，不计下降段得到的正差值总和是上界；在每个连续上涨段买入再卖出又能达到这个上界。

解题步骤

1. 令 n 为价格天数。若 k = 0 或不足两天，返回 0。
2. 若 k >= n / 2，累加所有正的相邻差值并直接返回。
3. 否则建立长度为 k+1 的 buy、sell 数组；sell 初始为 0，将 buy[1...k] 设为 -prices[0]。
4. 从第二天开始，依次更新每个 t 的 buy[t]，再更新 sell[t]。买入必须从 sell[t-1] 转移，为这次买入留出一笔额度。
5. 返回 sell[k]。最终必须空仓才表示交易已经完成，且这个状态已经包含少于 k 笔的所有选择。

代码实现

class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;

        if (k == 0 || n < 2) {
            return 0;
        }

        // 交易额度足够覆盖全部上涨段，可直接使用不限次结果。
        if (k >= n / 2) {
            int profit = 0;

            for (int i = 1; i < n; i++) {
                if (prices[i] > prices[i - 1]) {
                    profit += prices[i] - prices[i - 1];
                }
            }

            return profit;
        }

        int[] buy = new int[k + 1];
        int[] sell = new int[k + 1];

        for (int t = 1; t <= k; t++) {
            buy[t] = -prices[0];
        }

        for (int i = 1; i < n; i++) {
            for (int t = 1; t <= k; t++) {
                // 买入从前一次卖出转移，同日零收益动作不增加最优值。
                buy[t] = Math.max(buy[t], sell[t - 1] - prices[i]);
                sell[t] = Math.max(sell[t], buy[t] + prices[i]);
            }
        }

        return sell[k];
    }
}

func maxProfit(k int, prices []int) int {
    n := len(prices)
    if k == 0 || n < 2 {
        return 0
    }

    // 交易额度足够覆盖全部上涨段，可直接使用不限次结果。
    if k >= n/2 {
        profit := 0
        for i := 1; i < n; i++ {
            if prices[i] > prices[i-1] {
                profit += prices[i] - prices[i-1]
            }
        }
        return profit
    }

    buy := make([]int, k+1)
    sell := make([]int, k+1)
    for t := 1; t <= k; t++ {
        buy[t] = -prices[0]
    }

    for i := 1; i < n; i++ {
        for t := 1; t <= k; t++ {
            // 买入从前一次卖出转移，同日零收益动作不增加最优值。
            buy[t] = max(buy[t], sell[t-1]-prices[i])
            sell[t] = max(sell[t], buy[t]+prices[i])
        }
    }
    return sell[k]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

复杂度分析

设价格数组长度为 n。

• 时间复杂度：动态规划分支为 $O(nk)$，每天更新 k 组状态；交易额度足够时，贪心分支为 $O(n)$。
• 空间复杂度：动态规划分支为 $O(k)$，只保存当前状态；贪心分支为 $O(1)$。

关键点总结

[!green]

• 持股状态记录扣除买入成本后的现金余额，空仓状态才是已实现利润。
• 第 t 次买入需要从最多完成 t-1 笔交易的状态转移，卖出仍属于第 t 笔。
• “最多”使不交易和少交易始终合法，也是初始化方式与同日原地更新成立的前提。
• 交易额度足够时，只需要收集全部上涨收益，无需建立交易次数状态。

易错点总结

[!yellow]

• 买入误用 sell[t]：买入没有消耗新的交易额度，会让同一个 t 反复获得多笔收益；应使用 sell[t-1]。
• 把状态理解成恰好完成 t 笔交易：这会与所有 sell[t] 初始化为 0 冲突；本解法一直使用“最多”的含义。
• 只保留今天操作后的值：必须与旧值取 max，否则会丢失继续持有或继续空仓的更优选择。
• 把持股状态作为答案：buy[k] 仍包含未卖出的股票，最终应返回空仓状态 sell[k]。
• 不限次分支累加负差值：下降段可以空仓避开，只累加正差值。

相似题目

题目	难度	关联与区别
123. 买卖股票的最佳时机 III	困难	最多两笔交易是本题k=2的特例，按交易次数维护持有与空仓状态。
122. 买卖股票的最佳时机 II	中等	当k足够大时，交易次数限制不再起作用，可退化为无限次交易。
121. 买卖股票的最佳时机	简单	以持有状态和交易次数描述每天的最优收益；本题推广到 k 笔交易，该题只允许一次买卖。
309. 买卖股票的最佳时机含冷冻期	中等	以持有状态和交易次数描述每天的最优收益；本题推广到 k 笔交易，该题卖出后增加冷冻限制。
714. 买卖股票的最佳时机含手续费	中等	以持有状态和交易次数描述每天的最优收益；本题推广到 k 笔交易，该题在交易转移时计入手续费。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2025/90547968

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！