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(n²)
缺陷：当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框架解决，但需要根据条件调整状态定义

关键点：理解问题限制条件 → 定义状态 → 建立状态转移方程 → 优化空间复杂度

”`