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

HipHope
781 阅读11分钟

本文题解 leetcode 如下：

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

  • 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
}


avatar
文章
阅读
粉丝