[Leetcode 123] 买卖股票的最佳时机 III

type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算能获取的最大利润。
最多可以完成两笔交易, 且不能同时参与多笔交易(即必须在再次购买前出售掉之前的股票)。
 
示例 1:
示例 2:
示例 3:
示例 4:
 

解法一:暴力枚举

我们先从最直观的角度想: 既然只能买卖两次,那不就是把价格数组切成两段嘛?
第一段做第一次买卖,第二段做第二次买卖。
举个例子,比如 [3,3,5,0,0,3,1,4],我们可以在不同的天数中间分一刀,比如:
  • 第 0~3 天是第一笔交易;
  • 第 4~7 天是第二笔交易。
那么我们就可以:
  1. 枚举所有可能的分割点;
  1. 对每一段都算一次“买卖股票的最佳时机(只能买卖一次)”;
  1. 两段的利润加起来,取最大值。
复杂度
  • 时间:O(n²),因为每次分割都要重新遍历一遍。会超时。
  • 空间:O(1)。

解法二:动态规划 (推荐)

因为题目限制最多只能做两次交易,所以我们最多会经历四个操作阶段:
  1. 第一次买入(buy1)
      • 可能在前一天已经买过;
      • 或者今天刚买。
      所以取两种情况中的最大值: buy1 = max(buy1, -price)
      (因为买入要花钱,所以利润是负的。)
  1. 第一次卖出(sell1)
      • 可能昨天就已经卖掉;
      • 或者今天卖。
        • 今天卖的话,你之前必须处于买入状态:
      sell1 = max(sell1, buy1 + price)
  1. 第二次买入(buy2)
      • 可能昨天已经买了;
      • 或者今天买;
        • 今天买就得用第一次卖出的利润再去买:
      buy2 = max(buy2, sell1 - price)
  1. 第二次卖出(sell2)
      • 可能昨天已经卖完;
      • 或者今天卖;
        • 今天卖时,你手上之前得有第二次的买入状态:
      sell2 = max(sell2, buy2 + price)
整个交易顺序必须是: 买 → 卖 → 买 → 卖
我们用四个变量来记录截至当前天数时,在这四种状态下我们能得到的最大利润。
 
在开始之前,我们可以初始化为:
  • buy1 = -∞:因为还没买;
  • sell1 = 0:还没卖,利润是 0;
  • buy2 = -∞:还没第二次买;
  • sell2 = 0:还没第二次卖。
复杂度
  • 时间:O(n),我们只遍历一遍价格数组;
  • 空间:O(1),只用了 4 个变量。

解法三:动态规划数组版

用标准 DP 数组形式,写成二维 DP 表。
假设 dp[i][k][0/1] 表示:
  • 到第 i 天;
  • 最多允许做 k 次交易;
  • 0/1 表示手中是否持有股票(0:没持有,1:持有);
  • 状态值表示最大利润。
状态转移方程
  • dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + price[i]) # 今天没股票
  • dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - price[i]) # 今天有股票
复杂度
  • 时间:O(n × K),这里只有两次交易,所以其实还是 O(n);
  • 空间:O(n × K × 2),可以用滚动数组优化到 O(K)。
上一篇
[Leetcode 122] 买卖股票的最好时间 II
下一篇
[Leetcode 124] 二叉树中的最大路径和