题目描述(困难难度)

188. Best Time to Buy and Sell Stock IV - 图1

买卖股票续集,前边是 121 题122 题123 题 ,这道题的意思是,给一个数组代表股票每天的价格。你最多可以买入卖出 K 次,但只有卖出了才可以再次买入,求出最大的收益是多少。

解法一

直接按照前边题推出来的动态规划的方法做了,大家可以先到 121 题122 题123 题 看一下。

123 题 要求最多买卖两次,最终优化的出的代码如下。

  1. public int maxProfit(int[] prices) {
  2. if (prices.length == 0) {
  3. return 0;
  4. }
  5. int K = 2;
  6. int[] dp = new int[K + 1];
  7. int min[] = new int[K + 1];
  8. for (int i = 1; i <= K; i++) {
  9. min[i] = prices[0];
  10. }
  11. for (int i = 1; i < prices.length; i++) {
  12. for (int k = 1; k <= K; k++) {
  13. min[k] = Math.min(prices[i] - dp[k - 1], min[k]);
  14. dp[k] = Math.max(dp[k], prices[i] - min[k]);
  15. }
  16. }
  17. return dp[K];
  18. }

之前我们已经抽象出了一个变量 K 代表最多买卖 K 次,所以这里的话我们只需要把函数传过来的参数赋值给 K 即可。

  1. public int maxProfit(int k, int[] prices) {
  2. if (prices.length == 0) {
  3. return 0;
  4. }
  5. int K = k;
  6. int[] dp = new int[K + 1];
  7. int min[] = new int[K + 1];
  8. for (int i = 1; i <= K; i++) {
  9. min[i] = prices[0];
  10. }
  11. for (int i = 1; i < prices.length; i++) {
  12. for (int kk = 1; kk <= K; kk++) {
  13. min[kk] = Math.min(prices[i] - dp[kk - 1], min[kk]);
  14. dp[kk] = Math.max(dp[kk], prices[i] - min[kk]);
  15. }
  16. }
  17. return dp[K];
  18. }

但事情果然没有这么简单,内存超限了。

188. Best Time to Buy and Sell Stock IV - 图2

分析一下原因,我们申请了两个 K+1 大的数组,当 K 太大的时候就超出了内存的限制。

第一反应是因为数组需要消耗连续的内存空间,然后我又把数组改成链表进行了尝试,虽然没报超内存的错误,但直接报了超时的错误,原因也很简单,就是因为我们很多的随机存取,链表的话不易操作。现在再想想,有点儿傻,因为这个内存超限应该是 leetcode 的限制,而不是物理内存上真的不够了,所以数组改链表不会解决这个问题的。

怎么减小 K 的大小呢?为什么 K 会那么大那么大。仔细想想,其实 K 太大是没有意义的,如果我们数组的大小是 n,然后一天买,一天卖,我们最多就是 n/2 次交易(买入然后卖出算一次交易)。所以当 K 大于 n/2 的时候是没有意义的,所以我们可以再给 K 赋值的时候和 n/2 比较,选择较小的值赋值给 K

  1. public int maxProfit(int k, int[] prices) {
  2. if (prices.length == 0) {
  3. return 0;
  4. }
  5. int K = Math.min(k, prices.length / 2);
  6. int[] dp = new int[K + 1];
  7. int min[] = new int[K + 1];
  8. for (int i = 1; i <= K; i++) {
  9. min[i] = prices[0];
  10. }
  11. for (int i = 1; i < prices.length; i++) {
  12. for (int kk = 1; kk <= K; kk++) {
  13. min[kk] = Math.min(prices[i] - dp[kk - 1], min[kk]);
  14. dp[kk] = Math.max(dp[kk], prices[i] - min[kk]);
  15. }
  16. }
  17. return dp[K];
  18. }

然后去逛 Discuss 的时候突然想到,如果我们最多交易 K 次,而 K 又达到了 n/2,也就是最多的交易次数,那不就代表着我们可以交易任意次吗,交易任意次这不就是 122 题 讨论的吗。所以代码可以再优化一下。

  1. public int maxProfit(int k, int[] prices) {
  2. if (prices.length == 0) {
  3. return 0;
  4. }
  5. //K 看做任意次,转到 122 题
  6. if (k >= prices.length / 2) {
  7. return maxProfit(prices);
  8. }
  9. int K = k;
  10. int[] dp = new int[K + 1];
  11. int min[] = new int[K + 1];
  12. for (int i = 1; i <= K; i++) {
  13. min[i] = prices[0];
  14. }
  15. for (int i = 1; i < prices.length; i++) {
  16. for (int kk = 1; kk <= K; kk++) {
  17. min[kk] = Math.min(prices[i] - dp[kk - 1], min[kk]);
  18. dp[kk] = Math.max(dp[kk], prices[i] - min[kk]);
  19. }
  20. }
  21. return dp[K];
  22. }
  23. //122 题代码
  24. public int maxProfit(int[] prices) {
  25. int profit = 0;
  26. for (int i = 1; i < prices.length; i++) {
  27. int sub = prices[i] - prices[i - 1];
  28. if (sub > 0) {
  29. profit += sub;
  30. }
  31. }
  32. return profit;
  33. }

时间复杂度:O(nk)

空间复杂度:O(k)

解法二

原本以为这道题也就结束了,但 Discuss 区总是人外有人,天外有天,有人提出了崭新的解法,并且时间复杂度上进行了优化。参考 这里-time-8ms-Accepted-Solution-with-Detailed-Explanation-(C%2B%2B)) ,分享一下。

为了得到最高的收益,我们肯定会选择在波谷买入,然后在波峰卖出。第 v 天买入,第 p 天卖出,我们记做 (v,p)

188. Best Time to Buy and Sell Stock IV - 图3

所以我们所有可能的交易就是选取波谷、波峰,如上图,也就是 (0,1)(2,4)(5,6)。然后我们把这些交易所得的收益 prices[p] - prices[v] 依次放入数组中。把收益降序排序,选取前 k 个加起来,就是题目让我们所求的了,即最多进行 k 次交易时的最大收入。

  1. //定义一个结构,存储一次交易的买入卖出时间
  2. class Transaction {
  3. int valley;
  4. int peek;
  5. Transaction(int v, int p) {
  6. valley = v;
  7. peek = p;
  8. }
  9. }
  10. public int maxProfit(int k, int[] prices) {
  11. if(k == 0){
  12. return 0;
  13. }
  14. Stack<Transaction> stack = new Stack<>();
  15. List<Integer> profit = new ArrayList<>();
  16. int v;
  17. int p = -1;
  18. int n = prices.length;
  19. while (true) {
  20. v = p + 1;
  21. //寻找波谷
  22. while (v + 1 < n && prices[v] > prices[v + 1]) {
  23. v++;
  24. }
  25. p = v;
  26. //寻找波峰
  27. while (p + 1 < n && prices[p] <= prices[p + 1]) {
  28. p++;
  29. }
  30. //到达最后,结束寻找
  31. if (p == v) {
  32. break;
  33. }
  34. //将这次的波谷、波峰存入
  35. stack.push(new Transaction(v, p));
  36. }
  37. //遍历所有的买入、卖出,计算其收益
  38. while (!stack.isEmpty()) {
  39. Transaction pop = stack.pop();
  40. profit.add(prices[pop.peek] - prices[pop.valley]);
  41. }
  42. int ret = 0;
  43. //如果能够进行的交易数 K 大于我们存的交易数,就把所有收益累加
  44. if (k >= profit.size()) {
  45. for (int i = 0; i < profit.size(); i++) {
  46. ret += profit.get(i);
  47. }
  48. } else {
  49. //将收益从大到小排序
  50. Collections.sort(profit, new Comparator<Integer>() {
  51. @Override
  52. public int compare(Integer n1, Integer n2) {
  53. return n2 - n1;
  54. }
  55. });
  56. //选取前 k 个
  57. for (int i = 0; i < k; i++) {
  58. ret += profit.get(i);
  59. }
  60. }
  61. return ret;
  62. }

当然事情并不会这么简单,上边的情况是最理想的,在每次的波谷买入、波峰卖出,但对于下边的情况就会有些特殊了。

188. Best Time to Buy and Sell Stock IV - 图4

如果按照上边的算法,我们会将 (0,1)(2,3) 存入。如果进行两次交易,当然也是没有问题的,刚好就是这两次的收益相加。但如果进行一次交易呢?

很明显我们应该在第 0 天买入,在第 3 天卖出,所以我们应该将 (0,3) 存入。也就是当有新的交易 (2,3) 来的时候我们要和栈顶的交易 (0,1) 的波峰波谷进行比较,如果波谷大于之前的波谷,并且波峰也大于之前的波峰,两次交易就需要合并为 (0,3)

接下来的问题就是我们栈中只存了 (0,3) 这一次交易,那么算收益的时候,如果可以进行两次交易,那该怎么办呢?这也是这个解法最巧妙的地方了。

假如两次交易的时间分别是 (v1,p1)(v2,p2) ,那么

如果最多进行一次交易,那么最大收益就是 prices[p2] - prices[v1]

如果最多进行两次交易,那么最大收益就是 prices[p1] - prices[v1] + prices[p2] - prices[v2],进行一下变换 (prices[p2] - prices[v1]) + (prices[p1] - prices[v2]),第一个括号括起来的就是进行一次交易的最大收益,所以相对于只进行一次交易,我们的收益增加了第二个括号括起来的 prices[p1] - prices[v2],所以我们只需要在合并两次交易的时候,把 prices[p1] - prices[v2] 存到 profit 数组中即可。

举个具体的例子,假如股票价格数组是 1,4,2,6,然后我们有一个 stack 去存每次的交易,profit 去存每次交易的收入。

我们会把 6 - 1 = 54 - 2 = 2存入profit 中。

这样如果最多进行一次交易,从 profit 中选取最大的收益,我们刚好得到就是 5

如果最多进行两次交易,从 profit 中选取前二名的收益,我们就得到 5 + 2 = 7,刚好等价于 (4 - 1) + (6 - 2) = 7

  1. while (!stack.isEmpty() && prices[p] >= prices[stack.peek().peek && prices[v] >= prices[stack.peek().valley]) {
  2. Transaction pop = stack.pop();
  3. //加入 prices[p1] - prices[v2] 的收益
  4. profit.add(prices[pop.peek] - prices[v]);
  5. //买入点更新为前一次的买入点
  6. v = pop.valley;
  7. }

至于为什么要用 while 循环,因为和之前的合并之后,完全可能继续合并,比如下边的例子。

188. Best Time to Buy and Sell Stock IV - 图5

一开始 (2,3) 不能和 (0,1) 合并,但当 (4,5) 来时候,先和 (2,3) 合并为 (2,5),再和 (0,1)合并为 (0,5)

还有一种情况,如果新加入的交易的买入点低于栈顶交易的买入点,我们要把栈顶元素出栈。比如下图的例子。

188. Best Time to Buy and Sell Stock IV - 图6

首先是 (0,1) 入栈,然后是 (2,3) 入栈。接着 (4,5) 入栈,此时我们应该将 (2,3) 出栈,原因有两点。

第一,因为新来的交易买入点更低,未来如果有交易可以和 (2,3) 合并,那么一定可以和 (4,5) 合并。并且和 (4,5)合并后的收益会更大。

第二,因为栈顶的元素是已经不能合并的交易,而每次我们是和栈顶进行合并,所以新来的交易完全可能会和栈顶之前的元素进行合并交易,因此我们要把旧的栈顶元素出栈。就比如上图的中例子,把 (2,3) 出栈以后,我们可以把 (4,5)(0,1) 进行合并。

  1. //当前的买入点比栈顶的低
  2. while (!stack.isEmpty() && prices[v] <= prices[stack.peek().valley]) {
  3. Transaction pop = stack.pop();
  4. profit.add(prices[pop.peek] - prices[pop.valley]);
  5. }

至于为什么要用 while 循环,因为有可能需要连续出栈,比如下图的例子。

188. Best Time to Buy and Sell Stock IV - 图7

(6,7)来的时候,要把 (4,5)(2,3) 依次出栈。

综上所述,我们要把新的交易的买入点和栈顶的买入点比较,如果当前的买入点更低,要把栈顶的元素出栈。然后再判断,卖出点是否高于栈顶元素的卖出点,如果更高的话,要把当前交易和栈顶的交易合并。

代码的话,整体都不需要变化,只需要在新的交易入栈之前执行一些出栈和合并交易的操作。

  1. class Transaction {
  2. int valley;
  3. int peek;
  4. Transaction(int v, int p) {
  5. valley = v;
  6. peek = p;
  7. }
  8. }
  9. public int maxProfit(int k, int[] prices) {
  10. if(k == 0){
  11. return 0;
  12. }
  13. Stack<Transaction> stack = new Stack<>();
  14. List<Integer> profit = new ArrayList<>();
  15. int v;
  16. int p = -1;
  17. int n = prices.length;
  18. while (true) {
  19. v = p + 1;
  20. while (v + 1 < n && prices[v] > prices[v + 1]) {
  21. v++;
  22. }
  23. p = v;
  24. while (p + 1 < n && prices[p] <= prices[p + 1]) {
  25. p++;
  26. }
  27. if (p == v) {
  28. break;
  29. }
  30. //新的交易的买入点更低,要把栈顶的元素出栈
  31. while (!stack.isEmpty() && prices[v] <= prices[stack.peek().valley]) {
  32. Transaction pop = stack.pop();
  33. profit.add(prices[pop.peek] - prices[pop.valley]);
  34. }
  35. //当前交易和栈顶交易是否能合并
  36. while (!stack.isEmpty() && prices[p] >= prices[stack.peek().peek]) {
  37. Transaction pop = stack.pop();
  38. profit.add(prices[pop.peek] - prices[v]);
  39. v = pop.valley;
  40. }
  41. stack.push(new Transaction(v, p));
  42. }
  43. while (!stack.isEmpty()) {
  44. Transaction pop = stack.pop();
  45. profit.add(prices[pop.peek] - prices[pop.valley]);
  46. }
  47. int ret = 0;
  48. if (k >= profit.size()) {
  49. for (int i = 0; i < profit.size(); i++) {
  50. ret += profit.get(i);
  51. }
  52. } else {
  53. Collections.sort(profit, new Comparator<Integer>() {
  54. @Override
  55. public int compare(Integer n1, Integer n2) {
  56. return n2 - n1;
  57. }
  58. });
  59. for (int i = 0; i < k; i++) {
  60. ret += profit.get(i);
  61. }
  62. }
  63. return ret;
  64. }

时间复杂度的话,计算交易的时候需要 O(n) ,然后找出前 k 笔最大的交易的话用到了排序,如果是快速排序,那么就是 O(nlog(n)),所以总的来说就是 O(nlog(n))

时间复杂度上我们还是可以优化的,在求前 k 笔最大的交易,我们可以用大小为 k 的优先队列存储,优先队列在 23 题 的时候也有用过。

  1. //相当于最小堆,队列头始终队列中是最小的元素
  2. PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
  3. for (int i = 0; i < profit.size(); i++) {
  4. if (i < k) {
  5. queue.add(profit.get(i));
  6. } else {
  7. int peek = queue.peek();
  8. //当前收益大于栈顶元素,将栈顶元素弹出,然后将当前元素加入队列
  9. if (profit.get(i) > peek) {
  10. queue.poll();
  11. queue.add(profit.get(i));
  12. }
  13. }
  14. }
  15. while (!queue.isEmpty()) {
  16. ret += queue.poll();
  17. }

优先队列的出栈入栈时间复杂度都是 O(log(k)),我们遍历了收益数组,这样的话时间复杂度就是 O(nlog(k)) 了。

对于解法一,其实就是之前买卖股票的解法。但解法二是真的太强了,不容易想到,但想到的人真是太厉害了。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话,可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法,强烈推荐一个我之前学过的课程,可以点击 这里 查看详情