LeetCode 有一组经典的股票算法题,基本可以使用贪心或者动态规划来解决,这里做一个题解的汇总。

题目 描述
121.买卖股票的最佳时机 只能卖一次
122.买卖股票的最佳时机 II 可以买卖多次
123.买卖股票的最佳时机 III 最多卖 2 次
188.买卖股票的最佳时机 IV 最多卖 K 次
309.最佳买卖股票时机含冷冻期 买卖多次,卖出有一天冷却期
714.买卖股票的最佳时机含手续费 买卖多次,卖出有一天冷却期

121.买卖股票的最佳时机

题目描述

给定一个数组 prices ,它的第  i 个元素  prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

思路 1:暴力算法

func maxProfit_1(prices []int) int {
	ans := 0
	for i := 0; i < len(prices); i++ {
		for j := i + 1; j < len(prices); j++ {
			ans = max(ans, prices[j]-prices[i])
		}
	}
	return ans
}
  • 时间复杂度:O(n^2)
  • 可能复杂度:O(1)

思路 2:贪心算法

func maxProfit_2(prices []int) int {
	ans, lowPrice := 0, prices[0]
	for i := 0; i < len(prices); i++ {
		ans = max(ans, prices[i]-lowPrice)
		lowPrice = min(lowPrice, prices[i])
	}
	return ans
}
  • 时间复杂度:O(n)
  • 可能复杂度:O(1)

思路 3:动态规划

func maxProfit_3(prices []int) int {
	dp, n := make([][2]int, len(prices)), len(prices)
	dp[0][0], dp[0][1] = -prices[0], 0
	for i := 1; i < n; i++ {
		dp[i][0] = max(dp[i-1][0], -prices[i])
		dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i])
	}
	return dp[n-1][1]
}
  • 时间复杂度:O(n)
  • 可能复杂度:O(n)

122.买卖股票的最佳时机 II

题目描述

假设你有一个数组,其中第 i 个元素表示第 i 天某个股票的价格。 设计一种算法以找到最大利润,可以完成任意多次交易,但必须先购买股票再出售股票,不能同时多次交易。

题解 1:贪心算法

func maxProfit_1(prices []int) int {
	ans := 0
	for i := 1; i < len(prices); i++ {
		if prices[i] > prices[i-1] {
			ans += prices[i] - prices[i-1]
		}
	}
	return ans
}
  • 时间复杂度:O(n)
  • 可能复杂度:O(1)

题解 2:动态规划

func maxProfit_2(prices []int) int {
	dp, n := make([][2]int, len(prices)), len(prices)
	dp[0][0], dp[0][1] = -prices[0], 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][1]
}
  • 时间复杂度:O(n)
  • 可能复杂度:O(n)

123.买卖股票的最佳时机 III

题目描述

给你一个数组,第 ii 个元素表示第 ii 天股票的价格。 你最多可以交易两次。 请设计一个算法,求最大收益。

注意:必须先买再卖,且每天只能买或者卖一次。

题解 1:动态规划

func maxProfit_1(prices []int) int {
	dp, n := make([][5]int, len(prices)), len(prices)
	dp[0][1], dp[0][3] = -prices[0], -prices[0]
	for i := 1; i < n; i++ {
		dp[i][0] = dp[i-1][0]
		dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])
		dp[i][2] = max(dp[i-1][2], dp[i-1][1]+prices[i])
		dp[i][3] = max(dp[i-1][3], dp[i-1][2]-prices[i])
		dp[i][4] = max(dp[i-1][4], dp[i-1][3]+prices[i])
	}
	return dp[n-1][4]
}
  • 时间复杂度:O(n)
  • 可能复杂度:O(n)

188. 买卖股票的最佳时机 IV

题目描述

假设你有一个数组,其中第 i 个元素表示第 i 天某个股票的价格。 设计一种算法以找到最大利润,可以完成最多 k 次交易,但必须先购买股票再出售股票,不能同时多次交易。

题解 1:动态规划

func maxProfit_1(k int, prices []int) int {
	n, dp := len(prices), [][]int{}
	for i := 0; i < n; i++ {
		dp = append(dp, make([]int, k*2+1))
	}
	for i := 1; i < k*2; i += 2 {
		dp[0][i] = -prices[0]
	}
	for i := 1; i < n; i++ {
		for j := 0; j < k*2; j += 2 {
			dp[i][j+1] = max(dp[i-1][j+1], dp[i-1][j]-prices[i])
			dp[i][j+2] = max(dp[i-1][j+2], dp[i-1][j+1]+prices[i])
		}
	}
	return dp[n-1][k*2]
}
  • 时间复杂度:O(n)
  • 可能复杂度:O(n)

309. 最佳买卖股票时机含冷冻期

题目描述

你有一个数组,第 i 个元素是第 i 天股票的价格。 设计一个算法求最大利润。你可以进行任意次交易,即多次买入和卖出股票,但有如下限制:

  • 不能同时进行多笔交易,即再次买入股票时,必须已经卖掉现有的股票。
  • 在卖掉股票后,在下一天不能买入股票,即冷却一天。

题解 1:动态规划

func maxProfit(prices []int) int {
	dp, n := make([][4]int, len(prices)), len(prices)
	dp[0][0], dp[0][1] = -prices[0], 0
	for i := 1; i < n; i++ {
		dp[i][0] = max(dp[i-1][0], max(dp[i-1][3], dp[i-1][1])-prices[i])
		dp[i][1] = max(dp[i-1][1], dp[i-1][3])
		dp[i][2] = dp[i-1][0] + prices[i]
		dp[i][3] = dp[i-1][2]
	}
	return max(dp[n-1][3], max(dp[n-1][1], dp[n-1][2]))
}
  • 时间复杂度:O(n)
  • 可能复杂度:O(n)

714. 买卖股票的最佳时机含手续费

题目描述

给定一组某一 stock 在每一天的价格,买卖次数不限,每次买入必须在卖出之后,且每次卖出时都需要 fee 的手续费,求解最大的收益。

题解 1:贪心

func maxProfit_1(prices []int, fee int) int {
	ans, minPrice := 0, prices[0]
	for _, v := range prices {
		if v < minPrice {
			minPrice = v
		} else if v > minPrice && v > minPrice+fee {
			ans += v - minPrice - fee
			minPrice = v - fee
		}
	}
	return ans
}
  • 时间复杂度:O(1)
  • 空间复杂度:O(1)

题解 2:动态规划

func maxProfit_2(prices []int, fee int) int {
	dp, n := make([][2]int, len(prices)), len(prices)
	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]-fee)
		dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])
	}
	return dp[n-1][0]
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)