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)