LeetCode如何解決買賣股票的最佳時機問題

# LeetCode如何解決買賣股票的最佳時機問題

## 問題概述

買賣股票的最佳時機（Best Time to Buy and Sell Stock）是LeetCode上經典的動態規劃問題系列，包含6種變體（如含冷凍期、含手續費等）。本文將以**基礎版（121題）**和**進階版（122題）**為例，詳解解決思路和代碼實現。

> 題目121基礎描述：給定一個數組 `prices`，其中 `prices[i]` 是股票第 `i` 天的價格。你只能選擇**某一天買入**并**在未來的某一天賣出**，求最大利潤。

## 一、暴力解法（不推薦）

直接雙重循環計算所有可能的買賣組合：

```python
def maxProfit(prices):
    max_profit = 0
    for i in range(len(prices)):
        for j in range(i+1, len(prices)):
            profit = prices[j] - prices[i]
            if profit > max_profit:
                max_profit = profit
    return max_profit

時間復雜度：O(n2)
缺陷：當n=10?時會超時。

二、動態規劃解法（基礎版）

核心思路

1. 狀態定義：記錄歷史最低價 min_price
2. 狀態轉移：每日比較當前價與歷史最低價的差值

def maxProfit(prices):
    min_price = float('inf')
    max_profit = 0
    for price in prices:
        if price < min_price:
            min_price = price
        elif price - min_price > max_profit:
            max_profit = price - min_price
    return max_profit

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

三、進階問題（122題：多次交易）

進階描述：可以完成多次交易（但必須在再次購買前出售掉之前的股票）

解法1：貪心算法

只要后一天比前一天貴就進行交易：

def maxProfit(prices):
    profit = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[i-1]:
            profit += prices[i] - prices[i-1]
    return profit

時間復雜度：O(n)

解法2：動態規劃

定義二維DP數組： - dp[i][0] 第i天持有現金時的最大利潤 - dp[i][1] 第i天持有股票時的最大利潤

def maxProfit(prices):
    n = len(prices)
    dp = [[0]*2 for _ in range(n)]
    dp[0][0], dp[0][1] = 0, -prices[0]
    for i in range(1, n):
        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[-1][0]

優化空間版本：

def maxProfit(prices):
    cash, hold = 0, -prices[0]
    for price in prices[1:]:
        cash, hold = max(cash, hold + price), max(hold, cash - price)
    return cash

四、其他變體問題

1. 含手續費（714題）

在賣出時扣除手續費：

def maxProfit(prices, fee):
    cash, hold = 0, -prices[0]
    for price in prices[1:]:
        cash = max(cash, hold + price - fee)
        hold = max(hold, cash - price)
    return cash

2. 含冷凍期（309題）

賣出后需等待一天：

def maxProfit(prices):
    n = len(prices)
    dp = [[0]*3 for _ in range(n)]  # 0:持有 1:冷凍 2:未持有
    dp[0][0] = -prices[0]
    for i in range(1, n):
        dp[i][0] = max(dp[i-1][0], dp[i-1][2] - prices[i])
        dp[i][1] = dp[i-1][0] + prices[i]
        dp[i][2] = max(dp[i-1][2], dp[i-1][1])
    return max(dp[-1][1], dp[-1][2])

五、通用DP框架

對于所有股票問題，可使用統一模板：

# 初始化
dp = [[[0]*2 for _ in range(k+1)] for __ in range(n)]
# 狀態轉移
for i in range(1, n):
    for j in range(1, k+1):
        dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i])
        dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i])

六、復雜度對比

總結

1. 單次交易問題轉化為尋找最大差值
2. 多次交易優先考慮貪心算法
3. 復雜條件（冷凍期、手續費等）使用狀態機DP
4. 所有問題都可以用統一DP框架解決，但需要根據條件調整狀態定義

關鍵點：理解問題限制條件 → 定義狀態 → 建立狀態轉移方程 → 優化空間復雜度

”`