188-买卖股票的最佳时机 IV(Best Time to Buy and Sell Stock IV)
发表于：2021-12-03 | 分类： 困难
字数统计: 439 | 阅读时长: 2分钟 | 阅读量：

原文链接: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv

英文原文

You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k.

Find the maximum profit you can achieve. You may complete at most k transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

 

Example 1:

Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:

Input: k = 2, prices = [3,2,6,5,0,3]
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

 

Constraints:

  • 0 <= k <= 100
  • 0 <= prices.length <= 1000
  • 0 <= prices[i] <= 1000

中文题目

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

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

 

示例 1：

输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

示例 2：

输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
     随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

 

提示：

  • 0 <= k <= 100
  • 0 <= prices.length <= 1000
  • 0 <= prices[i] <= 1000

通过代码

高赞题解

前言

本题有一种基于 wqs 二分且时间复杂度相较于常规的动态规划 $O(nk)$ 更优秀的做法。

wqs 二分最初由王钦石在他的 2012 年国家集训队论文 [1] 中提出，而从 IOI 2016 的 Aliens 题目开始，这种方法开始逐步在竞赛圈中有了一定的地位。在国内我们一般称为「wqs 二分」，而在国外一般称为「Alien Trick」。

由于最初的论文讲解得比较简洁，因此作者在学习 wqs 二分时还同时参考了 [2] 以及 [3] 两篇文章，其中 [2] 对于 wqs 二分能够解决的问题类型给出了明确的定义，[3] 使用图解形象化地展示了 wqs 二分的本质。

对于本篇题解而言，我会在讲解题目的同时讲解 wqs 二分。不过要想读懂这篇题解（以及给出的参考资料），读者需要至少掌握以下的知识点：

  • 动态规划基础
  • 斜率、截距
  • 凸包、上凸壳

同时这里直接抽象地给出 wqs 二分适用的题目类型：

给定 $n$ 个物品，我们需要在其中恰好选择 $k$ 个，并且需要最大化收益。设对应的收益为 $g_k$，那么需要满足在最大化收益的前提下，每多选择一个物品，额外产生的收益是单调递减的，也就是 $g_{k+1}-g_k \leq g_k-g_{k-1}$。同时，如果我们对物品的选择数量没有限制，即 $k$ 不存在，那么我们应当能够快速地计算出最大的收益，以及达到最大的收益需要选择的物品数量。

方法一：wqs 二分

思路与算法

我们设恰好完成 $k$ 笔交易时，能够获取的最大收益为 $g_k$，那么

$$
g_{k+1}-g_k \leq g_k-g_{k-1}
$$

是成立的。我们可以这样想：我们每额外增加一笔交易 $g_k \to g_{k+1}$，那么这一笔交易一定不会比上一笔交易 $g_{k-1} \to g_k$ 产生的收益高，否则我们就可以交换这两笔交易，使得 $g_k$ 更大，那么就与 $g_k$ 是恰好完成 $k$ 笔交易时的最大收益这个事实相矛盾了。

如果我们把 $(k, g_k)$ 看成平面直角坐标系上的点，那么这些点就组成了一个上凸壳，如下图所示：

188-1.png{:width=70%}

形象化地说，在最初的时候，随着 $k$ 的增加，我们可以不断地通过买入卖出获得额外的正收益。但 $k$ 到了一定的阈值之后，如果再强制进行交易，那么我们只能以高价买入，低价卖出，每多一笔交易，就会获得额外的负收益。因此，$(k, g_k)$ 对应的图像就是一个上凸壳，即随着 $k$ 的增大，以 $(k, g_k)$ 与 $(k+1, g_{k+1})$ 为端点的线段的斜率是单调递减的。

虽然我们并不知道 $g_k$ 的值到底是多少（否则我们就可以直接返回正确答案了），但是我们知道 $(k, g_k)$ 对应的图像的形状。wqs 二分的妙处就在于此，通过对斜率进行二分，求出 $g_k$ 的值。

188-2.png{:width=70%}

假设我们枚举了某斜率 $c$，如上图所示，我们画出所有经过 $(k, g_k)$ 并且斜率为 $c$ 的直线。为了美观性，我们只画出了 $k \in [1, 5]$ 的直线。我们发现，斜率为 $c$ 的直线与上凸壳相切在了 $k’=4$ 的绿色点位置，根据上凸壳的性质，经过绿色点的这条直线与 $y$ 轴的截距也是所有斜率为 $c$ 的直线中最大的。

那么这个「截距」代表了什么？对于经过 $(k, g_k)$ 而言，经过它并且斜率为 $c$ 的直线在 $y$ 轴上的截距是

$$
g_k - k \cdot c
$$

而 $g_k$ 恰好包含了 $k$ 笔交易带来的收益，如果将这个收益减去 $k \cdot c$，那么就可以看做是每一笔交易都包含了 $c$ 的手续费！当每一笔交易都包含了 $c$ 的手续费时，如果规定了恰好进行 $k$ 笔交易，那么最大的收益就是经过 $(k, g_k)$ 并且斜率为 $c$ 的直线在 $y$ 轴上的截距。此时，$(k’, g_k’)$ 对应的截距是大，因此**如果我们不限制进行的交易次数，那么最终得到的最大收益就是 $g_k’-k’ \cdot c$**。

这个子问题就是 714. 买卖股票的最佳时机含手续费，我们可以在 $O(n)$ 的时间内求出这个子问题的最大收益，并且可以顺便求出具体的交易次数。因此，如果我们选择了一个合适的斜率 $c’$，使得其与上凸壳相切在了某一个我们需要的 $(k, g_k)$ 的位置（例如本题中给出的参数 $k$），这样我们就可以在 $O(n)$ 的时间内直接求出不限制交易次数的最大收益，并且我们知道它实际上就是交易了 $k$ 次。

这个神奇的方法怎么抽象地进行理解呢？我们可以这样想：随着斜率（手续费）$c$ 的增大，我们会趋向于进行更少次数的交易，在最大收益的前提下，交易的次数是具有单调性的，这也是由上凸壳保证的。例如在极端情况下 $c=\infty$，我们不会进行任何一笔交易。因此我们就可以对 $c$ 进行二分，如果找到了恰好进行 $k$ 次交易的 $c$，那么我们就得到了正确的答案。

然而上面的方法存在两个小问题：

  • 第一个问题是读者一定会发现的：本题中我们限制的是最多进行 $k$ 次交易，而不是恰好进行 $k$ 次交易，那么上面的方法还适用吗？

  • 我们是通过对二分来找出与题目中给定的 $k$ 对应的 $(k, g_k)$ 相切的斜率 $c$。那么二分的上下界如何确定？并且这个斜率 $c$ 一定存在吗？

细节

我们在「细节」部分来回答上面的两个小问题。

对于第一个问题，我们分两种情况进行讨论：

  • 如果 $(k, g_k)$ 所在的位置是上凸壳的左半部分（即斜率大于等于 $0$ 的部分），那么我们就可以使用上面的方法得到答案，这是因为最优的答案一定是进行 $k$ 次交易的；

  • 如果 $(k, g_k)$ 所在的位置是上凸壳的右半部分（即斜率小于 $0$ 的部分），那么我们通过二分是没有办法找到斜率 $c$ 并且计算出对应的 $(k, g_k)$ 的。具体的做法可以在第二个问题中得到解释，也就是我们可以规定二分查找的上下界。

对于第二个问题，我们规定二分查找的下界为 $1$，这样当 $(k, g_k)$ 所在的位置是上凸壳的右半部分时，二分查找就会失败。二分查找的上界可以设定得宽松一些，由于每一条线段的斜率都不会超过数组 $\textit{prices}$ 中给定价格的最大值，因此可以将上界设定为这个最大值。如果二分查找失败，那么说明最大收益对应的交易次数是严格小于题目中给定的 $k$ 的，这就说明交易次数的限制并不是瓶颈，而价格才是，因此我们可以直接使用 122. 买卖股票的最佳时机 II 中的方法计算出最终答案。

不过可能会有另外一种情况导致二分查找失败，即如果上凸壳上有若干连续的且斜率相等的线段，例如下图所示，那么在查找到该斜率 $c$ 时，我们只会计算出一个对应的 $k$ 值（例如图中绿色的点），然而实际上是有不止一个 $k$ 值是满足要求的 （例如图中红色的点），这些点对应的截距都是最大值，那么如果题目中给定的 $k$ 对应的是红色的点，那么二分查找就会失败。

188-3.png{:width=70%}

对于这种情况，我们可以在求解子问题时，尽可能地多进行交易，求解出最大的那个 $k$ 值。从本质上来说，红色的点与绿色的点之间实际上只是相差了若干笔收益为 $0$ 的交易而已，因此它们之间都是可以互相转换的。

最后需要注意的是：我们求解子问题时得到的收益是 $g_k - k \cdot c$，所以别忘了将这个收益加上 $k \cdot c$ 才会得到最终的答案。

代码

[sol1-C++]
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if (prices.empty()) {
            return 0;
        }

        int n = prices.size();
        // 二分查找的上下界
        int left = 1, right = *max_element(prices.begin(), prices.end());
        // 存储答案，如果值为 -1 表示二分查找失败
        int ans = -1;
        while (left <= right) {
            // 二分得到当前的斜率（手续费）
            int c = (left + right) / 2;

            // 使用与 714 题相同的动态规划方法求解出最大收益以及对应的交易次数
            int buyCount = 0, sellCount = 0;
            int buy = -prices[0], sell = 0;

            for (int i = 1; i < n; ++i) {
                if (sell - prices[i] >= buy) {
                    buy = sell - prices[i];
                    buyCount = sellCount;
                }
                if (buy + prices[i] - c >= sell) {
                    sell = buy + prices[i] - c;
                    sellCount = buyCount + 1;
                }
            }

            // 如果交易次数大于等于 k，那么可以更新答案
            // 这里即使交易次数严格大于 k，更新答案也没有关系，因为总能二分到等于 k 的
            if (sellCount >= k) {
                // 别忘了加上 kc
                ans = sell + k * c;
                left = c + 1;
            }
            else {
                right = c - 1;
            }
        }

        // 如果二分查找失败，说明交易次数的限制不是瓶颈
        // 可以看作交易次数无限，直接使用贪心方法得到答案
        if (ans == -1) {
            ans = 0;
            for (int i = 1; i < n; ++i) {
                ans += max(prices[i] - prices[i - 1], 0);
            }
        }

        return ans;
    }
};
[sol1-Python3]
class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        if not prices:
            return 0

        n = len(prices)
        # 二分查找的上下界
        left, right = 1, max(prices)
        # 存储答案，如果值为 -1 表示二分查找失败
        ans = -1

        while left <= right:
            # 二分得到当前的斜率（手续费）
            c = (left + right) // 2

            # 使用与 714 题相同的动态规划方法求解出最大收益以及对应的交易次数
            buyCount = sellCount = 0
            buy, sell = -prices[0], 0

            for i in range(1, n):
                if sell - prices[i] >= buy:
                    buy = sell - prices[i]
                    buyCount = sellCount
                if buy + prices[i] - c >= sell:
                    sell = buy + prices[i] - c
                    sellCount = buyCount + 1

            # 如果交易次数大于等于 k，那么可以更新答案
            # 这里即使交易次数严格大于 k，更新答案也没有关系，因为总能二分到等于 k 的
            if sellCount >= k:
                # 别忘了加上 kc
                ans = sell + k * c
                left = c + 1
            else:
                right = c - 1

        # 如果二分查找失败，说明交易次数的限制不是瓶颈
        # 可以看作交易次数无限，直接使用贪心方法得到答案
        if ans == -1:
            ans = sum(max(prices[i] - prices[i - 1], 0) for i in range(1, n))

        return ans

复杂度分析

  • 时间复杂度：$O(n \log C)$，其中 $n$ 是数组 $\textit{prices}$ 的长度，$C$ 是数组 $\textit{prices}$ 中的最大值，在本题中 $C \leq 1000$。

  • 空间复杂度：$O(1)$。

参考资料

[1] 浅析一类二分方法
[2] Wqs 二分
[3] 关于 WQS 二分算法以及其一个细节证明

统计信息

通过次数 提交次数 AC比率
95832 241890 39.6%

提交历史

提交时间 提交结果 执行时间 内存消耗 语言

相似题目

题目 难度
买卖股票的最佳时机 简单
买卖股票的最佳时机 II 中等
买卖股票的最佳时机 III 困难
动态规划 数组
上一篇:
187-重复的DNA序列(Repeated DNA Sequences)
下一篇:
189-轮转数组(Rotate Array)
本文目录
本文目录
    •
    本站总访问量： 次 |
    Copyright © 2020 - 2021 枫奇丶宛南 | Powered by Hexo | Theme Bamboo