122. 買賣股票的最佳時機 II

描述

給你一個整數數組 prices ，其中 prices[i] 表示某支股票第 i 天的價格。

在每一天，你可以決定是否購買和/或出售股票。你在任何時候 最多 只能持有 一股 股票。你也可以先購買，然后在 同一天 出售。

返回 你能獲得的 最大 利潤 。

示例 1

輸入：prices = [7,1,5,3,6,4]
輸出：7
解釋：在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5 - 1 = 4。
隨后，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6 - 3 = 3。
最大總利潤為 4 + 3 = 7 。

示例 2

輸入：prices = [1,2,3,4,5]
輸出：4
解釋：在第 1 天（股票價格 = 1）的時候買入，在第 5 天 （股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5 - 1 = 4。
最大總利潤為 4 。

示例 3

輸入：prices = [7,6,4,3,1]
輸出：0
解釋：在這種情況下, 交易無法獲得正利潤，所以不參與交易可以獲得最大利潤，最大利潤為 0。

提示

• 1 <= prices.length <= 3 * 10^4
• 0 <= prices[i] <= 10^4

解題思路

這道題的核心思想是：由于可以進行多次買賣，我們需要抓住每一次股價上漲的機會來獲得最大利潤。

核心觀察

1. 無限制交易：可以進行任意次數的買賣
2. 同一天可以買賣：先買再賣，或者先賣再買
3. 最多持有一股：不能同時持有多股
4. 目標：獲得最大總利潤

關鍵洞察

貪心策略：只要明天的價格比今天高，就今天買入明天賣出。這樣可以捕獲所有的價格上漲段。

算法實現

方法1：貪心算法（推薦）

func maxProfitGreedy(prices []int) int {maxProfit := 0for i := 1; i < len(prices); i++ {if prices[i] > prices[i-1] {maxProfit += prices[i] - prices[i-1]}}return maxProfit
}

原理：累加所有相鄰的正收益。

時間復雜度：O(n)
空間復雜度：O(1)

方法2：動態規劃

func maxProfitDP(prices []int) int {n := len(prices)dp := make([][2]int, n)dp[0][0] = 0          // 不持有股票dp[0][1] = -prices[0] // 持有股票for i := 1; i < n; i++ {dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])  // 賣出dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])  // 買入}return dp[n-1][0]
}

狀態定義：

• dp[i][0]：第i天結束后不持有股票的最大利潤
• dp[i][1]：第i天結束后持有股票的最大利潤

時間復雜度：O(n)
空間復雜度：O(n)

方法3：動態規劃（空間優化）

func maxProfitDPOptimized(prices []int) int {hold := -prices[0]  // 持有股票的最大利潤sold := 0           // 不持有股票的最大利潤for i := 1; i < len(prices); i++ {newSold := max(sold, hold+prices[i])newHold := max(hold, sold-prices[i])sold, hold = newSold, newHold}return sold
}

時間復雜度：O(n)
空間復雜度：O(1)

方法4：波峰波谷法

找到所有的波谷和波峰，在波谷買入，在波峰賣出。

func maxProfitPeakValley(prices []int) int {i, maxProfit := 0, 0for i < len(prices)-1 {// 找波谷for i < len(prices)-1 && prices[i+1] <= prices[i] {i++}valley := prices[i]// 找波峰for i < len(prices)-1 && prices[i+1] >= prices[i] {i++}peak := prices[i]maxProfit += peak - valley}return maxProfit
}

算法分析

復雜度對比

方法	時間復雜度	空間復雜度	優點	缺點
貪心算法	O(n)	O(1)	簡潔高效，易理解	需要理解貪心思想
動態規劃	O(n)	O(n)	狀態轉移清晰	空間開銷大
動態規劃優化	O(n)	O(1)	空間效率高	狀態維護復雜
波峰波谷	O(n)	O(1)	直觀易懂	代碼稍復雜
狀態機	O(n)	O(1)	邏輯清晰	理解成本高

算法流程圖

貪心算法證明

命題：對于任意價格序列，貪心策略（累加所有正差值）能夠獲得最大利潤。

證明：

1. 可行性：貪心策略產生的交易序列是合法的（每次買入后必須賣出才能再次買入）
2. 最優性：任何其他交易策略的利潤都不會超過貪心策略

設最優解包含交易 (buy_i, sell_i)，其總利潤為：

profit = Σ(sell_i - buy_i)

貪心策略的利潤為：

greedy_profit = Σ(prices[i] - prices[i-1]) for all i where prices[i] > prices[i-1]

可以證明：greedy_profit >= profit

示例分析

示例1：prices = [7,1,5,3,6,4]

貪心分析：
第1天: 7 -> 第2天: 1，下跌，不交易
第2天: 1 -> 第3天: 5，上漲，利潤 = 5-1 = 4
第3天: 5 -> 第4天: 3，下跌，不交易  
第4天: 3 -> 第5天: 6，上漲，利潤 = 6-3 = 3
第5天: 6 -> 第6天: 4，下跌，不交易總利潤 = 4 + 3 = 7

可視化：

價格走勢圖：7 |●|  \5 |   ●|    \3 |     ●---●|          \1 | ●         ●+--+--+--+--+--+1  2  3  4  5  天數交易策略：第2天買入(1) -> 第3天賣出(5)：利潤4第4天買入(3) -> 第5天賣出(6)：利潤3

動態規劃詳解

狀態轉移方程

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])

狀態轉移圖

DP狀態表（示例）

對于 prices = [7,1,5,3,6,4]：

天數	價格	不持有股票	持有股票	決策
0	7	0	-7	初始狀態
1	1	0	-1	在第1天買入更優
2	5	4	-1	第2天賣出獲利4
3	3	4	1	第3天買入
4	6	7	1	第4天賣出獲利3
5	4	7	3	保持不持有狀態

實際應用

1. 投資策略

• 短線交易：頻繁買賣獲取價差
• 波段操作：在價格波動中獲利
• 算法交易：程序化交易系統

2. 類似問題

• 買賣股票的最佳時機系列題目
• 背包問題的變種
• 區間調度問題

3. 實際約束

在實際投資中還需考慮：

• 交易手續費
• 稅收影響
• 市場流動性
• 價格滑點

代碼實現要點

邊界條件處理

if len(prices) <= 1 {return 0  // 少于2個價格無法交易
}

數組越界防護

for i := 1; i < len(prices); i++ {  // 從第2個元素開始// 安全訪問 prices[i] 和 prices[i-1]
}

整數溢出考慮

對于極大數據，考慮使用 int64 或添加溢出檢查。

練習建議

1. 理解貪心思想：為什么累加所有正差值是最優的？
2. 掌握狀態轉換：DP中兩個狀態如何相互轉換？
3. 空間優化技巧：如何從O(n)優化到O(1)？
4. 擴展思考：如果有交易手續費怎么辦？
5. 變種練習：限制交易次數的情況如何處理？

相關題目

• 121. 買賣股票的最佳時機（只能交易一次）
• 123. 買賣股票的最佳時機 III（最多交易兩次）
• 188. 買賣股票的最佳時機 IV（最多交易k次）
• 309. 最佳買賣股票時機含冷凍期（含冷凍期）
• 714. 買賣股票的最佳時機含手續費（含手續費）

完整題解代碼

package mainimport ("fmt""time"
)// 方法1：貪心算法 - 抓住每一次上漲機會
// 時間復雜度：O(n)，空間復雜度：O(1)
func maxProfitGreedy(prices []int) int {if len(prices) <= 1 {return 0}maxProfit := 0// 只要第二天比第一天價格高，就在第一天買入，第二天賣出for i := 1; i < len(prices); i++ {if prices[i] > prices[i-1] {maxProfit += prices[i] - prices[i-1]}}return maxProfit
}// 方法2：動態規劃
// 時間復雜度：O(n)，空間復雜度：O(n)
func maxProfitDP(prices []int) int {if len(prices) <= 1 {return 0}n := len(prices)// dp[i][0] 表示第i天不持有股票的最大利潤// dp[i][1] 表示第i天持有股票的最大利潤dp := make([][2]int, n)// 初始狀態dp[0][0] = 0          // 第0天不持有股票，利潤為0dp[0][1] = -prices[0] // 第0天買入股票，利潤為-prices[0]for i := 1; i < n; i++ {// 第i天不持有股票：可能是前一天就不持有，或者前一天持有今天賣出dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])// 第i天持有股票：可能是前一天就持有，或者前一天不持有今天買入dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])}// 最后一天不持有股票肯定比持有股票利潤更大return dp[n-1][0]
}// 方法3：動態規劃（空間優化）
// 時間復雜度：O(n)，空間復雜度：O(1)
func maxProfitDPOptimized(prices []int) int {if len(prices) <= 1 {return 0}// 只需要記錄當前的狀態，不需要整個數組hold := -prices[0] // 持有股票的最大利潤sold := 0          // 不持有股票的最大利潤for i := 1; i < len(prices); i++ {newSold := max(sold, hold+prices[i]) // 今天賣出newHold := max(hold, sold-prices[i]) // 今天買入sold = newSoldhold = newHold}return sold
}func max(a, b int) int {if a > b {return a}return b
}func main() {testCases := [][]int{{7, 1, 5, 3, 6, 4}, // 預期輸出: 7{1, 2, 3, 4, 5},    // 預期輸出: 4{7, 6, 4, 3, 1},    // 預期輸出: 0{1, 2, 1, 2, 1},    // 預期輸出: 2{5},                // 預期輸出: 0{},                 // 預期輸出: 0}fmt.Println("=== 買賣股票的最佳時機 II - 多種解法測試 ===")fmt.Println()methods := []struct {name stringfn   func([]int) int}{{"貪心算法", maxProfitGreedy},{"動態規劃", maxProfitDP},{"動態規劃(優化)", maxProfitDPOptimized},}for i, testCase := range testCases {fmt.Printf("測試用例 %d: %v\n", i+1, testCase)for _, method := range methods {start := time.Now()result := method.fn(testCase)duration := time.Since(start)fmt.Printf("  %s: %d (用時: %v)\n", method.name, result, duration)}fmt.Println()}// 算法思路演示fmt.Println("=== 算法思路演示 ===")demonstrateGreedyApproach([]int{7, 1, 5, 3, 6, 4})
}func demonstrateGreedyApproach(prices []int) {fmt.Printf("\n貪心算法思路演示:\n")fmt.Printf("價格數組: %v\n", prices)maxProfit := 0transactions := []string{}for i := 1; i < len(prices); i++ {if prices[i] > prices[i-1] {profit := prices[i] - prices[i-1]maxProfit += profittransaction := fmt.Sprintf("第%d天買入(%d) -> 第%d天賣出(%d), 利潤: %d", i, prices[i-1], i+1, prices[i], profit)transactions = append(transactions, transaction)}}fmt.Println("交易記錄:")for _, transaction := range transactions {fmt.Printf("  %s\n", transaction)}fmt.Printf("總利潤: %d\n", maxProfit)
}