leetcode Go语言题解之买卖股票系列

本文题解 leetcode 如下：

• 121 Best Time to Buy and Sell Stock
• 122 Best Time to Buy and Sell Stock II
• 123 Best Time to Buy and Sell Stock III
• 188 Best Time to Buy and Sell Stock IV
• 309 Best Time to Buy and Sell Stock with Cooldown
• 714 Best Time to Buy and Sell Stock with Transaction Fee

其实上述题目背景基本是一致的： 给定一个非负整数数组，这个数组表示一段时间内某个股票的价格变动情况，我们需要求解交易可获得的最大收益，注意不能同时参与多笔交易（必须在再次购买股票前出售掉之前的股票） ，但上述题目对交易的限制条件是不同的：

• 121 : 至多进行一次交易
• 122 : 对交易次数不做限制
• 123 : 至多进行两次交易
• 188 : 至多进行 k 次交易
• 309 : 对交易次数不做限制，但在卖股票当天的后一天无法买入股票（技能冷却一天）
• 714 : 对交易次数不做限制，但每次卖股票的当天将收取值为 fee 的交易手续费

对于不同的限制条件，将导致不同的解题策略

121 : 至多进行一次交易

题目链接 : leetcode.com/problems/be…

Example 1:
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
复制代码

至多进行一次交易的情况是最直观的，要想获得最大利润， 显然就是要在数组中要找两个点，前者处于低谷，后者处于高峰，且两者的差值最大（低价买高价卖）

如下图所示，以折线图的角度看，从第 1 天买入股票，到第 6 天卖股票，得到的收益是最大的

当然如果是股票狂跌的情况，自然是找不到这样的两个点的

假设 i 为交易天数的迭代变量，此时我们可以定义两个变量：

• minPrice : 从第 0 天到第 i 天股票出现的最低价格
• result : 从第 0 天到第 i 天卖掉价格为 minPrice 的股票所产生的最大利润

根据上述定义，在未进行交易的初始情况下，可设 minPrice 为无穷大，result 为 0

const (
	INT_MX = 1 << 31
)

// 低价买，高价卖
func maxProfit(prices []int) int {
	result, minPrice := 0, INT_MX
	for _, price := range prices {
		minPrice = minV(minPrice, price)
		result = maxV(result, price-minPrice)
	}
	return result
}


func minV(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func maxV(a, b int) int {
	if a > b {
		return a
	}
	return b
}
复制代码

122 : 对交易次数不做限制

题目链接 : leetcode.com/problems/be…

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

Example 2:
Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.

Example 3:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
复制代码

本题对交易次数不做限制，如下图所示，如果仅允许交易一次，那么我们选的交易点是在 a 点买入，在 d 点卖出，但现在我们并不限制任何购买次数，因此交易策略就很简单了：每逢低谷（a 和 c 点）买股票，每逢高峰（b 和 d 点）卖股票

从图中可以轻易看到：

b-a+d-c = b+(d-a)-c > d-a
复制代码

说白了， 如果一个很大的上坡路可以分解为若干个上坡路和下坡路，那么这些上坡路的海拔差之和肯定大于等于总体上坡路的海拔差，因为有了低谷对海拔差之和的贡献

// 低价买入，高价卖出
// 找出所有的 peak 和 valley 即可
func maxProfit(prices []int) int {
	n := len(prices)
	if n <= 1 {
		return 0
	}
	index, peak, valley, result := 0, prices[0], prices[0], 0
	for index < n-1 {
		// 找到第一个 prices[index] 小于 prices[index+1]
		for index < n-1 && prices[index] >= prices[index+1] {
			index++
		}
		valley = prices[index]
		// 找到第一个 prices[index] 大于 prices[index+1]
		for index < n-1 && prices[index] <= prices[index+1] {
			index++
		}
		peak = prices[index]
		result += (peak - valley)
	}
	return result
}
复制代码

其实此题没必要如此大费周章，因为不限制交易次数， 所以从直觉上说，只要有得赚（第 i 天的股价大于第 i-1 天的股价），就直接买第 i-1 天的股票，卖第 i 天的股票

func maxProfit(prices []int) int {
	n := len(prices)
	result := 0
	for i := 1; i < n; i++ {
		if prices[i] > prices[i-1] {
			result += prices[i] - prices[i-1]
		}
	}
	return result
}
复制代码

上述解法相对更直观

123 : 至多进行两次交易

题目链接 : leetcode.com/problems/be…

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

Example 2:
Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.

Example 3:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
复制代码

此题实际上相当于 121 的增强版

在 121 中，限制条件是至多交易 1 次，所以要找最低谷和最高峰做差，而本题其实是类似的，只是至多交易 2 次

回顾 121 的状态方程，我们定义了两个状态变量:

• minPrice : 从第 0 天到第 i 天股票出现的最低价格
• result : 从第 0 天到第 i 天卖掉价格为 minPrice 的股票所产生的最大利润

minPrice = minV(minPrice, price)
result = maxV(result, price-minPrice)
复制代码

123 这道题也可以用 121 的方式来做，只不过此时需要定义 4 个变量：

• firstHold : 第一次持有股票的最大收益
• firstCash : 第一次卖股票的最大收益
• secondHold : 第二次持有股票的最大收益
• seconCash : 第二次卖股票的最大收益

状态转移方程如下：

// 第一次持有股票得到的最大收益
// 如果 prices[i] 刚好是最低谷那 firstHold 就一直不变了
// 跟 121 的 minPrice 其实是一个概念，只是这里用负值表示
firstHold = maxV(firstHold, 0-prices[i])
// 第一次卖掉股票得到的最大收益（可以在同一天买卖）
firstCash = maxV(firstCash, firstHold+prices[i])
// 第二次购买股票，包含第一次卖掉股票的最大收益，这里的 firstCash 很关键
secondHold = maxV(secondHold, firstCash-prices[i])
// 第二次卖掉股票得到的最大收益
secondCash = maxV(secondCash, secondHold+prices[i])
复制代码

以 example 1 为例 [3,3,5,0,0,3,1,4]

其实可以看到，第二次交易是依赖于第一次交易的，而第一次交易的策略刚好与 121 至多交易 1 次的策略一致

188 : 至多进行 k 次交易

题目链接 : leetcode.com/problems/be…

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

Example 2:
Input: [3,2,6,5,0,3], k = 2
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.
复制代码

这题就没办法单纯画图来描述了，但如果懂得 123 题的逻辑，那么这题也就简单了，类比就完事了

在 123 题里我们的状态转移方程如下：

firstHold = maxV(firstHold, 0-prices[i])
firstCash = maxV(firstCash, firstHold+prices[i])
secondHold = maxV(secondHold, firstCash-prices[i])
secondCash = maxV(secondCash, secondHold+prices[i])
复制代码

而此题其实同理，比如如果 k = 3，有：

thirdHold = maxV(thirdHold, secondCash-prices[i])
thirdCash = maxV(thirdCash, thirdHold+prices[i])
复制代码

所以实际上我们可以定义 hold 数组和 cash 数组来表示

hold[k] = maxV(hold[k], cash[k-1]-price)
cash[k] = maxV(cash[k], hold[k]+price)
复制代码

另外如果 k 的值大于或等于给定数组的一半，也就是 k >= len(array)/2 ，那么此问题就转换为 122，也就是交易任意次数了

具体代码如下所示：

const (
	INT_MX = 1 << 31
)

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

func maxProfit(k int, prices []int) int {
	n, result := len(prices), 0
	if k >= n/2 {
		for i := 1; i < n; i++ {
			if prices[i] > prices[i-1] {
				result += (prices[i] - prices[i-1])
			}
		}
	} else {
		hold, cash := make([]int, k+1), make([]int, k+1)
		for i := 0; i <= k; i++ {
			hold[i], cash[i] = -INT_MX, 0
		}
		for _, price := range prices {
			for i := 1; i <= k; i++ {
				hold[i] = maxV(hold[i], cash[i-1]-price)
				cash[i] = maxV(cash[i], hold[i]+price)
			}
		}
		result = cash[k]
	}
	return result
}

复制代码

309 : 对交易次数不做限制，但在卖股票当天的后一天无法买入股票（技能冷却一天）

题目链接 : leetcode.com/problems/be…

Example:
Input: [1,2,3,0,2]
Output: 3 
Explanation: transactions = [buy, sell, cooldown, buy, sell]
复制代码

Example 的交易策略如下图所示：

在此题中我们将定义 6 个状态变量（实际上是 3 个，另外 3 个的区别只是天数不同）：

• a0 : 第 i 天没有持有股票的最佳收益
• a1 : 第 i 天持有股票后的最佳收益
• a2 : 第 i 天卖出股票后的最佳收益
• t0 : 第 i-1 天没有持有股票的最佳收益
• t1 : 第 i-1 天持有股票后的最佳收益
• t2 : 第 i-1 天卖出股票后的最佳收益

上述这么解释可能有点抽象，以状态图解释：

从上述状态图，我们可以写出状态转移方程：

a0 = maxV(t0, t2)
a1 = maxV(t1, t0-prices[i])
a2 = t1 + prices[i]
复制代码

第 i 天的最佳收益由第 i-1 天的最佳收益决定，所以算是比较典型的动态规划问题（重叠子问题、最优子结构）

可以看到最后迭代的结果就是从 a0 和 a2 两者中选最大值， 这里的 cooldown （技能冷却）体现在从 a2 到 a0 的状态转变中

初始化的情况，即 i=0 的时候，有：

// 第 0 天没有买股票
a0 = 0
// 第 0 天买股票
a1 = -prices[0]
// 第 0 天卖不了股票
a2 = 0
// t0、t1、t2 未定义
复制代码

当 i > 0 时：

• 分别初始化 t0、t1、t2 为 a0、a1、a2，然后再利用 t0、t1、t2 计算新的 a0、a1、a2
• a0 : 第 i 天没有持有股票的最佳收益，那有两种情况，取其最大值
  1. 继续不买股票，所以为第 i-1 天没有持有股票的最佳收益 -> t0
  2. 处于冷却期，因为第 i-1 天卖掉股票后的最佳收益，使得第 i 天进行技能冷却 -> t2
• a1 : 第 i 天持有股票后的最佳收益，同样也有两种情况，取其最大值
  1. 欢乐持股，所以为第 i-1 天持有股票后的最佳收益 -> t1
  2. 买入股票（从未持股到持股） -> t0-prices[i]
• a2 : 第 i 天卖出股票后的最佳收益，根据定义只能有一种情况 -> t1+prices[i]

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

// a0 : 代表没有买入股票的状态
// a1 : 代表买入后等待卖出的状态
// a2 : 代表从 a1 卖出股票的状态
func maxProfit(prices []int) int {
    if len(prices) <= 1 {
        return 0
    }
	a0, a1, a2 := 0, -prices[0], 0
	var t0, t1, t2 int
    for i := 1; i < len(prices); i++ {
		t0, t1, t2 = a0, a1, a2
		a0 = maxV(t0, t2)
		a1 = maxV(t1, t0-prices[i])
		a2 = t1 + prices[i]
	}
	return maxV(a0, a2)
}

复制代码

714 : 对交易次数不做限制，但在每次卖股票的当天将收取值为 fee 的交易手续费

题目链接 : leetcode.com/problems/be…

Example 1:
Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
Buying at prices[0] = 1
Selling at prices[3] = 8
Buying at prices[4] = 4
Selling at prices[5] = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
复制代码

此题与上一题类似，也属于动态规划问题，但定义的状态相对简单，因此也更好理解些：

• currentCash : 第 i 天未持有股票时所获得的最大收益
• currentHold : 第 i 天持有股票时所获得的最大收益

状态图如下：

相应状态转移方程和代码如下：

// 买卖股票有两种状态，第 i 天结束后：
// 1. 未持有股票（观望股市，或者把先前持有股票卖了）
// 2. 持有股票（欢乐持股，或者买第 i 天的股票）
func maxProfit(prices []int, fee int) int {
    // 初始化为第 0 天，有两种情况：不买第 0 天的股票；买第 0 天的股票
    currentCash, currentHold := 0, -prices[0]
    for i := 1; i < len(prices); i++ {
        currentCash = maxV(currentCash, currentHold+prices[i]-fee)
        // 为什么这里可以用已经计算过的第 i 天的 currentCash
        // 去算 currentHold 呢？因为不限制购买次数
        // 完全可以当天卖再当天买，不影响最后的计算结果的
        currentHold = maxV(currentHold, currentCash-prices[i])
    }
    return currentCash
}复制代码