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 I...
本文題解 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 天沒有持有股票的最佳收益，那有兩種情況，取其最大值
- 繼續不買股票，所以為第 i-1 天沒有持有股票的最佳收益 -> t0
- 處於冷卻期，因為第 i-1 天賣掉股票後的最佳收益，使得第 i 天進行技能冷卻 -> t2
- a1 : 第 i 天持有股票後的最佳收益，同樣也有兩種情況，取其最大值
- 歡樂持股，所以為第 i-1 天持有股票後的最佳收益 -> t1
- 買入股票（從未持股到持股） -> 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
}複製程式碼