LeetCode 股票买卖 6 题分析

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

121.买卖股票的最佳时机

• Leetcode 题目地址
• Code

题目描述

给定一个数组 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

• Leetcode 题目地址
• Code

题目描述

假设你有一个数组，其中第 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

• Leetcode 题目地址
• Code

题目描述

给你一个数组，第 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

• Leetcode 题目地址
• Code

题目描述

假设你有一个数组，其中第 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. 最佳买卖股票时机含冷冻期

• Leetcode 题目地址
• Code

题目描述

你有一个数组，第 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. 买卖股票的最佳时机含手续费

• Leetcode 题目地址
• Code

题目描述

给定一组某一 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)