今天带来的是 LeetCode 的所有买卖股票最佳时机的系列题。在这篇文章中，可以熟练一次遍历思想以及单维、多维动态规划。

本文题目难度标识：🟩简单，🟨中等，🟥困难。

基本题干：买卖股票的最佳时机

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

1 次股票买卖定义为：选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。

你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

提示：prices.length>=1

下文中出现的买卖股票的问题都是基于此题干进行条件设置。

允许 0-1 次买卖

要求：至多允许 1 次买卖。求最大利润。

我们需要找出给定数组中两个数字之间的最大差值（即最大利润）。此外，第二个数字（卖出价格）必须大于第一个数字（买入价格）。

形式上，对于每组 ii 和 jj（其中 j>ij>i）我们需要找出 max(prices[j]-prices[i])。

暴力方法

此方法时间复杂度过高，将导致超时。
1
2
3
4
5
6
7
8
9
public int maxProfit(int[] prices) {
	int res = 0;
	for (int i = 0; i < prices.length - 1; i++) {
		for (int j = i + 1; j < prices.length; j++) {
			res = Math.max(res,prices[j] - prices[i]);
		}
	}
	return res;
}

复杂度分析：

  • 时间复杂度：O(n2)O(n^2)。循环运行 n(n−1)/2n(n-1)/2​ 次。
  • 空间复杂度：O(1)O(1)。只使用了常数个变量。

一次遍历

思考：假设我们要在第 i 卖股票，那么我们能赚多少钱呢？最好的愿望就是，我们是在在第 i 天之前的历史最低点买入的股票！

我们只要用一个变量记录一个历史最低价格 minprice，我们就可以假设自己的股票是在那天买的。那么我们在第 i 天卖出股票能得到的利润就是 prices[i] - minprice。

因此，我们只需要遍历价格数组一遍，记录历史最低点，然后在每一天考虑这么一个问题：如果我是在历史最低点买进的，那么我今天卖出能赚多少钱？当考虑完所有天数之时，我们就得到了最好的答案。

1
2
3
4
5
6
7
8
9
10
public int maxProfit(int[] prices) {
	int len = prices.length;
	int minprice = prices[0];
	int res = 0;
	for(int i=1;i<len;i++){
		res = Math.max(res,prices[i]-minprice);
		minprice = Math.min(min,prices[i]);
	}
	return res;
}

复杂度分析：

  • 时间复杂度：O(n)O(n)，只需要遍历一次。
  • 空间复杂度：O(1)O(1)，只使用了常数个变量。

这种一次遍历的做法基于了 前后缀分解的思想。

转换为最大子数组问题

这个题目还可以转变为 最大子数组问题，从而转为使用本文列举的动态规划、分治法等多种方案（点击链接即可直达本站文章查看解法）。我们可以从每日价格变化考察输入数据。第 i 天的价格变化定义为第 i-1 天的价格差，生成表 A’。问题求解变为求 A’ 的最大子数组。

例如：

image.png

允许任意次买卖系列

允许任意次买卖（无约束）

要求：允许任意次买卖。求最大利润。

贪心算法

思路：反正无限次买，薅住一个历史最低点卖出股票就行了。实际算出的数，就是第 i 天相较于第 i-1 天涨出的价格。注意，这个历史最低点是指从左到右遍历的历史最低点，不是全局历史最低点。

具体严格的贪心证明请看 LeetCode 题解。

1
2
3
4
5
6
7
public int maxProfit(int[] prices) {
	int res = 0;
	for(int i=1;i<prices.length;i++){
		res += Math.max(0,prices[i]-prices[i-1]);
	}
	return res;
}

需要说明的是，贪心算法只能用于计算最大利润，计算的过程并不是实际的交易过程。

复杂度分析：

  • 时间复杂度：O(n)O(n)，其中 n 为数组的长度。我们只需要遍历一次数组即可。
  • 空间复杂度：O(1)O(1)。只需要常数空间存放若干变量。

动态规划

请务必弄懂此处动态规划算法，为后续题目的解决打好基础。

题目要求每天交易结束后只可能存在手里有一支股票或者没有股票的状态。

定义状态 dp0[i] 表示第 i 天交易完后手里没有股票的最大利润，dp1[i] 表示第 i 天交易完后手里持有一支股票的最大利润（i 从 0 开始）。

状态转移方程：

  • dp0[i]=max{dp0[i-1],dp1[i-1]+prices[i]}：前一天不持有股票和前一天持有股票并今天卖出比较。
  • dp1[i]=max{dp1[i-1],dp0[i-1]-prices[i]}：前一天持有股票和前一天不持有股票但今天买入。

初始条件：状态定义我们可以知道第 0 天交易结束的时候 dp0[0]=0，dp1[0]=-prices[0]。

答案的选择：最后一天不持有股票的利润肯定比持有股票的多。所以答案返回 dp0[n-1]。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 基本DP
public int maxProfit(int[] prices) {
	int n = prices.length;
	int[] dp0 = new int[n];
	int[] dp1 = new int[n];
	dp0[0] = 0;
	dp1[0] = -prices[0];
	for (int i = 1; i < n; ++i) {
		dp0[i] = Math.max(dp0[i - 1], dp1[i - 1] + prices[i]);
		dp1[i] = Math.max(dp1[i - 1], dp0[i - 1] - prices[i]);
	}
	return dp0[n - 1];
}

复杂度分析：

  • 时间复杂度：O(n)O(n)，其中 n 为数组的长度。一共有 2n2n 个状态，每次状态转移的时间复杂度为 O(1)O(1)，因此时间复杂度为 O(2n)=O(n)O(2n)=O(n)。
  • 空间复杂度：O(n)O(n)。我们需要开辟 O(n)O(n) 空间存储动态规划中的所有状态。如果使用空间优化，空间复杂度可以优化至 O(1)O(1)。

下面给出一种更好理解的空间压缩算法：

1
2
3
4
5
6
7
8
9
10
11
12
// 空间压缩
public int maxProfit(int[] prices) {
	int dp0_old=0,dp1_old=-prices[0];
	int dp0,dp1;
	for(int i=1;i<prices.length;i++){
		dp0 = Math.max(dp0_old,dp1_old+prices[i]);
		dp1 = Math.max(dp1_old,dp0_old-prices[i]);
		dp0_old = dp0;
		dp1_old = dp1;
	}
	return dp0_old;
}

允许任意次买卖 + 手续费

要求：你可以无限次地完成交易，但是你每笔交易都需要付固定手续费 fee 。求最大利润。

思路：根据「买股票的最佳时机 II」的动态规划思路进行变动，稍微修改状态转移方程即可，至于什么时候进行缴费都行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 买下股票时缴费（dp1缴费）
public int maxProfit(int[] prices, int fee) {
	int dp0_old=0;
	int dp1_old=-prices[0]-fee;
	int dp0,dp1;
	for(int i=1;i<prices.length;i++){
		dp0 = Math.max(dp0_old,dp1_old+prices[i]);
		dp1 = Math.max(dp1_old,dp0_old-prices[i]-fee);
		dp0_old = dp0;
		dp1_old = dp1;
	}
	return dp0_old;
}

// 卖出股票时缴费（回归到dp0时缴费）
public int maxProfit(int[] prices, int fee) {
	int dp0_old=0;
	int dp1_old=-prices[0];
	int dp0,dp1;
	for(int i=1;i<prices.length;i++){
		dp0 = Math.max(dp0_old,dp1_old+prices[i]-fee);
		dp1 = Math.max(dp1_old,dp0_old-prices[i]);
		dp0_old = dp0;
		dp1_old = dp1;
	}
	return dp0_old;
}

允许任意次买卖 + 冷冻期

要求：你可以无限次地完成交易，但是卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。求最大利润。

思路：根据「买股票的最佳时机 II」的动态规划思路进行变动，在状态转移方程中 dp1[i]=max{dp1[i-1],dp0[i-2]-prices[i]} 的变化为，从原来的昨天未持有股票的最大利润 dp0[i-1]，改为 dp0[i-2]。这是因为如果选择 dp0[i-1]，你无法保证 dp0[i-1] 当天有没有卖出过股票（因为昨天卖出股票后今天就不能买）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 public int maxProfit(int[] prices) {
	int len = prices.length;
	if(len==1)return 0;
	if(len==2)return Math.max(0,prices[1]-prices[0]);
	int[] dp0 = new int[len];
	int[] dp1 = new int[len];
	dp0[0] = 0;
	dp0[1] = Math.max(0,prices[1]-prices[0]);
	dp1[0] = -prices[0];
	dp1[1] = Math.max(-prices[0],-prices[1]);
	for(int i=2;i<len;i++){
		dp0[i] = Math.max(dp0[i-1],dp1[i-1]+prices[i]);
		dp1[i] = Math.max(dp1[i-1],dp0[i-2]-prices[i]);
	}
	return dp0[len-1];
}
思考题：上面的代码还能进行空间压缩吗？

允许 0-2 次买卖

要求：至多 2 次买卖。求最大利润。

由于我们最多可以完成两笔交易，因此在任意一天结束之后，我们会处于以下五个状态中的一种：

  • 未进行过任何操作；
  • 只进行过一次买操作；
  • 进行了一次买操作和一次卖操作，即完成了一笔交易；
  • 在完成了一笔交易的前提下，进行了第二次买操作；
  • 完成了全部两笔交易。

由于第一个状态的利润显然为 0，因此我们可以不用将其记录。对于剩下的四个状态，我们分别将它们的最大利润记为 buy1，sell1，buy2 以及 sell2。

状态转移方程：

  • buy1​=max{buy1′​,-prices[i]}
  • sell1​=max{sell1′​,buy1′​+prices[i]}
  • buy2​=max{buy2′​,sell1′​-prices[i]}
  • sell2​=max{sell2′​,buy2′​+prices[i]}​
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int maxProfit(int[] prices) {
	int buy1p=-prices[0],buy2p=-prices[0],sell1p=0,sell2p=0;
	int buy1,buy2,sell1,sell2;
	for(int i=1;i<prices.length;i++){
		buy1 = Math.max(buy1p,-prices[i]);
		sell1= Math.max(sell1p,buy1p+prices[i]);
		buy2 = Math.max(buy2p,sell1p-prices[i]);
		sell2 = Math.max(sell2p,buy2p+prices[i]);
		buy1p = buy1;
		sell1p = sell1;
		buy2p = buy2;
		sell2p = sell2;
	}
	return Math.max(0,sell2p);
}

复杂度分析：

  • 时间复杂度：O(n)O(n)，其中 n 是数组 prices 的长度。
  • 空间复杂度：O(1)O(1)。
思考题：在上述代码中，还能不能简化掉 buy1,buy2,sell1,sell2 变量？为什么？

允许指定次数 k 次买卖

要求：你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。求最大利润。

思路：就是把「买股票的最佳时机 III」的动态规划扩展而已。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public int maxProfit(int k, int[] prices) {
	int len = prices.length;

	// k 取值的简化
	k=Math.min(k,len/2);
	k = k==0 ? 1 : k; // k 不能为 0
	
	int[] buyp= new int[k];
	for(int i=0;i<k;i++){
		buyp[i] = -prices[0];
	}
	int[] sellp= new int[k];
	int[] buy = new int[k];
	int[] sell = new int[k];
	for(int i=1;i<len;i++){
		for(int j=0;j<k;j++){
			// 处理初始情况
			if(j==0)
				buy[j] = Math.max(buyp[j],-prices[i]);
			else
				buy[j] = Math.max(buyp[j],sellp[j-1]-prices[i]);
			sell[j] = Math.max(sellp[j],buyp[j]+prices[i]);
		}
		for(int j=0;j<k;j++){
			buyp[j] = buy[j];
			sellp[j] = sell[j];
		}
	}
	return Math.max(0,sellp[k-1]);
}

上面的代码中出现了对 k 的简化，因为 n 天最多只能进行 ⌊n/2⌋⌊n/2⌋ 笔交易。因此我们可以将 k 对 ⌊n/2⌋⌊n/2⌋ 取较小值之后再进行动态规划。

思考题：上面的代码还能进行空间压缩吗？

复杂度分析：

  • 时间复杂度：O(nmin⁡(n,k))O(n\min (n,k))，其中 n 是数组 prices 的大小，即我们使用二重循环进行动态规划需要的时间。
  • 空间复杂度：O(nmin⁡(n,k))O(n\min(n,k)) 或 O(min⁡(n,k))O(\min (n,k))，取决于我们使用二维数组还是一维数组进行动态规划。

本文参考

  • 《算法导论》
  • LeetCode 相关题目的题解