004.买卖股票

• 121.买卖股票的最佳时机
  • 暴力
    • 时间复杂度：O(n^2)
    • 空间复杂度：O(1)
  • 贪心
    • 时间复杂度：O(n)
    • 空间复杂度：O(1)
  • 动态规划
    • 时间复杂度：O(n)
    • 空间复杂度：O(1)
• 122.买卖股票的最佳时机 II
  • 股票问题-贪心章节
• 123.买卖股票的最佳时机 III
• 188.买卖股票的最佳时机 IV
  • 思路同上
• 309.买卖股票的最佳时机含冷冻期
• 714.买卖股票的最佳时机含手续费
  • 股票问题-贪心章节

买卖股票的最佳时机 - 暴力 §

找最优间距

func maxProfit(prices []int) int {
	res := 0
 
	for i, v1 := range prices {
		for j := i + 1; j < len(prices); j++ {
			res = max(res, prices[j] - v1)
		}
	}
 
	return res
}

买卖股票的最佳时机 - 贪心 §

取最左最小值，取最右最大值，得到的差值就是最大利润

func maxProfit(prices []int) int {
	res := 0
	minn := math.MaxInt64
 
	for _, v := range prices {
		minn = min(minn, v)
		res = max(res, v - minn)
	}
 
	return res
}

买卖股票的最佳时机 - 动态规划 §

func maxProfit(prices []int) int {
	n := len(prices)
	if n == 0 {
		return 0
	}
 
	// dp: 所得最多现金
	dp := [2]int{
		-prices[0], // 持有股票
		0, // 不持有股票
	}
 
	for i := 1; i < n; i++ {
		dp = [2]int{
			// 只能买一次股票，所以这里是-prices[i]，而不是dp[1] - prices[i]
			max(dp[0], -prices[i]), // max(前一天就持有股票, 今天买股票)
			max(dp[1], dp[0] + prices[i]), // max(前一天就不持有股票, 今天卖股票)
		}
	}
 
	return dp[1] // dp[0]不可能比dp[1]大
}

买卖股票的最佳时机 III §

func maxProfit(prices []int) int {
	n := len(prices)
	if n == 0 {
		return 0
	}
	dp := [...]int{
		-prices[0], // 第一次持有股票
		0, // 第一次不持有股票（第一次卖掉股票）
		-prices[0], // 第二次持有股票，为什么初始化为 -prices[0]：相当于第一天买、卖、再买
		0, // 第二次不持有股票（第二次卖掉股票）
	}
 
	for i := 1; i < n; i++ {
		dp = [...]int{
			max(dp[0], -prices[i]),
			max(dp[1], dp[0] + prices[i]),
			max(dp[2], dp[1] - prices[i]),
			max(dp[3], dp[2] + prices[i]),
		}
	}
 
	// dp[0] < dp[1]
	// dp[2] < dp[3]
	// dp[1] <= dp[3]: 第i天买、卖、再买
	return dp[3]
}

买卖股票的最佳时机含冷冻期 §

func maxProfit(prices []int) int {
	n := len(prices)
	if n == 0 {
		return 0
	}
 
	dp := [...]int{
		-prices[0], // 持有股票
		0, // 不持有股票，不在冷却期
		0, // 不持有股票，在冷却期
	}
 
	for i := 1; i < n; i++ {
		dp = [...]int{
			// max(前一天就持有股票, 前一天不持有股票且不在冷却期，今天买)
			max(dp[0], dp[1] - prices[i]),
			// 前一天不持有股票
			max(dp[1], dp[2]),
			// max(前一天不持有股票, 前一天持有股票，今天卖)
			max(dp[1], dp[2], dp[0] + prices[i]),
		}
	}
 
	return max(dp[1], dp[2])
}