股票买卖

📌 核心概念

股票买卖问题是贪心算法的经典应用场景，不同限制条件对应不同的贪心策略。

核心思想：在允许的交易次数下，抓住每次价格上涨的机会。

💻 算法实现

🎯 经典应用

💡 解题技巧

2. 状态机思想

买入 -> 持有 -> 卖出 -> (冷冻期) -> 可买入

3. 优化技巧

# 优化1：k >= n/2时，等价于无限次交易
if k >= len(prices) // 2:
    return unlimited_transactions(prices)
 
# 优化2：空间优化（只保留前一个状态）
buy, sell = -prices[0], 0
for price in prices[1:]:
    buy, sell = max(buy, sell - price), max(sell, buy + price)

📊 复杂度分析

问题	时间复杂度	空间复杂度	方法
最佳时机I	O(n)	O(1)	贪心
最佳时机II	O(n)	O(1)	贪心
最佳时机III	O(n)	O(1)	状态机DP
最佳时机IV	O(nk)	O(k)	DP
含手续费	O(n)	O(1)	状态机DP
含冷冻期	O(n)	O(1)	状态机DP

Go 代码

// 买卖股票I
func maxProfit(prices []int) int {
    minPrice := math.MaxInt32
    maxProfit := 0
 
    for _, price := range prices {
        minPrice = min(minPrice, price)
        maxProfit = max(maxProfit, price-minPrice)
    }
 
    return maxProfit
}
 
// 买卖股票II
func maxProfit2(prices []int) int {
    profit := 0
 
    for i := 1; i < len(prices); i++ {
        if prices[i] > prices[i-1] {
            profit += prices[i] - prices[i-1]
        }
    }
 
    return profit
}
 
// 买卖股票含手续费
func maxProfitWithFee(prices []int, fee int) int {
    hold := -prices[0]
    cash := 0
 
    for i := 1; i < len(prices); i++ {
        cash = max(cash, hold+prices[i]-fee)
        hold = max(hold, cash-prices[i])
    }
 
    return cash
}
 
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
 
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

🎯 经典题目

题目	LeetCode	难度	关键点
买卖股票的最佳时机	121	简单	一次交易
买卖股票的最佳时机II	122	中等	无限次交易
买卖股票的最佳时机III	123	困难	两次交易
买卖股票的最佳时机IV	188	困难	k次交易
买卖股票含手续费	714	中等	手续费
买卖股票含冷冻期	309	中等	冷冻期
股票价格波动	2034	中等	堆+懒删除

---

返回：贪心算法