Leetcode股票买卖6题分析
Leetcode 上关于股票买卖的题目分析
121. Best Time to Buy and Sell Stock
题目描述
假设你有一个数组,其中第i个元素表示第i天某个股票的价格。 如果您只允许完成至多一笔交易(即买入一只股票并卖出一只股票),则设计一种算法以找到最大利润。 必须先购买股票再出售股票。
样例
Example 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第二天买(price = 1) ,在第五天卖 (price = 6), 利润 = 6-1 = 5.
Example 2:
输入: [7,6,4,3,1]
输出: 0
解释: 这个例子中没有完成交易。
题解1:暴力算法
思路:暴力2次循环找出解
复杂度
- 时间复杂度:O(n^2)
- 可能复杂度:O(1)
Code
func maxProfit1(prices []int) int {
maxprofit := 0
for i := 0; i < len(prices); i++ {
for j := i + 1; j < len(prices); j++ {
profit := prices[j] - prices[i]
if profit > maxprofit {
maxprofit = profit
}
}
}
return maxprofit
}
题解2:贪心算法
思路:利用贪心法的含义是选当前最优。遍历一次,更新当前最低价格和最高利润。
复杂度
- 时间复杂度:O(n)
- 可能复杂度:O(1)
Code
func maxProfit(prices []int) int {
profit, low := 0, prices[0]
for i := 0; i < len(prices); i++ {
// 当前收益
profit = max(profit, prices[i]-low)
// 记录最小单价
low = min(low, prices[i])
}
return profit
}
122. Best Time to Buy and Sell Stock II
题目描述
假设你有一个数组,其中第i个元素表示第i天某个股票的价格。 设计一种算法以找到最大利润,可以完成任意多次交易,但必须先购买股票再出售股票,不能同时多次交易。
样例
Example 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 第二天买(price = 1),第三天卖(price=5),利润为4;
第四天买(price = 3),第五天卖(price=6),利润为3。
Example 2:
输入: [1,2,3,4,5]
输出: 4
解释: 第一天买(price = 1),第五天卖(price=5),利润为4。
Example 3:
输入: [7,6,4,3,1]
输出: 0
解释: 这个例子中没有完成交易。
题解1:贪心算法
思路:一次循环分别记录最大利润
复杂度
- 时间复杂度:O(n)
- 可能复杂度:O(1)
Code
func maxProfit(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
}
题解2:动态规划
思路:利用一个N行2列的数组表示每天出售、卖出、的收益。
dp[i][0]
表示第i天未出售股票的利润dp[i][1]
表示第i天出售股票的利润- 状态转移
- 出售股票或者不做任何操作 ->
dp[i][0] = max(dp[i-1][1]+price[i],dp[i-1][0])
- 买入股票或者不做任何操作 ->
dp[i][1] = max(dp[i-1][0])-price[i],dp[i-1][1])
dp[0][0]=0,dp[0][1]=INT_MIN
复杂度
- 时间复杂度:O(n)
- 可能复杂度:O(n)
Code
func maxProfit2(prices []int) int {
// 初始化DP
n := len(prices)
dp := make([][]int, 0)
for i := 0; i <= n; i++ {
dp = append(dp, make([]int, 2))
}
dp[0][0], dp[0][1] = 0, math.MinInt32
profit_max := 0
for i := 0; i < n; i++ {
dp[i+1][0] = max(dp[i][1]+prices[i], dp[i][0])
dp[i+1][1] = max(dp[i][0]-prices[i], dp[i][1])
profit_max = max(profit_max, dp[i+1][0])
profit_max = max(profit_max, dp[i+1][1])
}
return profit_max
}
123. Best Time to Buy and Sell Stock III
题目描述
给你一个数组,第 ii 个元素表示第 ii 天股票的价格。 你最多可以交易两次。 请设计一个算法,求最大收益。
**注意:**必须先买再卖,且每天只能买或者卖一次。
样例
Example 1:
输入:[3,3,5,0,0,3,1,4]
输出:6
解释:一共交易两次:
第4天买(价格是0),第6天卖(价格是3),收益3;
第7天卖(价格是1),第8天卖(价格是4),收益3;
总共收益6。
Example 2:
输入:[1,2,3,4,5]
输出:4
解释:一共交易一次:
第1天买(价格是1),第5天卖(价格是5),收益4。
注意不能第1天买第3天卖,然后第3天买第5天卖,因为
每天只能进行买或者卖一种操作。
Example 3:
输入:[7,6,4,3,1]
输出:0
解释:不做任何交易,收益0。
题解1:动态规划
思路:在整个区间的每一点切开, 然后分别计算左子区间和右子区间的最大值,然后再用O(n)时间找到整个区间的最大值。
- 遍历一遍数组,求
[0,i−1][0,i−1
]区间的最大利润f(i)
,具体做法是找当前最低价格low
,判断是要以low
买入当天卖出,还是不动 - 从后往前遍历,求
[i,n−1][i,n−1]
区间的最大利润g(i)
,具体做法是找当前最高价格high
,判断是要当天买入以high
卖出,还是不动 - 遍历,求最大利润
max(f(i)+g(i))
复杂度
- 时间复杂度:O(n)
- 可能复杂度:O(n)
Code
func maxProfit(prices []int) int {
g, f := make([]int, len(prices)), make([]int, len(prices))
ans, n, low := 0, len(prices), prices[0]
for i := 1; i < n; i++ {
low = min(low, prices[i])
f[i] = max(f[i-1], prices[i]-low)
}
high := prices[n-1]
for i := n - 2; i >= 0; i-- {
high = max(high, prices[i])
g[i] = max(g[i+1], high-prices[i])
}
for i := 0; i < n; i++ {
ans = max(ans, f[i]+g[i])
}
return ans
}
188. Best Time to Buy and Sell Stock IV
题目描述
假设你有一个数组,其中第 ii 个元素表示第 ii 天某个股票的价格。 设计一种算法以找到最大利润,可以完成最多 k 次交易,但必须先购买股票再出售股票,不能同时多次交易。
样例
Example 1:
Input: [2,4,1], k = 2
Output: 2
解释: 第一天买入(price = 2),第二天售出 (price = 4), 利润 = 4-2 = 2.
Example 2:
Input: [3,2,6,5,0,3], k = 2
Output: 7
解释: 第二天买入(price = 2),第三天卖出 (price = 6), 利润 = 6-2 = 4.
接着第五天买入(price = 0),第六天卖出(price = 3), 利润 = 3-0 = 3.
题解1:动态规划
思路
复杂度
- 时间复杂度:O(n)
- 可能复杂度:O(n)
Code
309. Best Time to Buy and Sell Stock with Cooldown
题目描述
你有一个数组,第 i 个元素是第 i 天股票的价格。 设计一个算法求最大利润。你可以进行任意次交易,即多次买入和卖出股票,但有如下限制:
- 不能同时进行多笔交易,即再次买入股票时,必须已经卖掉现有的股票。
- 在卖掉股票后,在下一天不能买入股票,即冷却一天。
样例
Input: [1,2,3,0,2]
Output: 3
解释: 交易顺序为 = [买入, 卖出, 冷却, 买入, 卖出]
题解1:动态规划
思路
复杂度
- 时间复杂度:O(n)
- 可能复杂度:O(n)
Code
714. Best Time to Buy and Sell Stock with Transaction fee
题目描述
给定一组某一stock在每一天的价格,买卖次数不限,每次买入必须在卖出之后,且每次卖出时都需要fee的手续费,求解最大的收益。
样例
Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
Buying at prices[0] = 1
Selling at prices[3] = 8
Buying at prices[4] = 4
Selling at prices[5] = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8
题解1:动态规划
思路
复杂度
- 时间复杂度:O(n)
- 空间复杂度:O(1)
Code
func maxProfit(prices []int, fee int) int {
cash, hold := 0, -prices[0]
for i := 1; i < len(prices); i++ {
cash = max(cash, hold+prices[i]-fee)
hold = max(hold, cash-prices[i])
}
return cash
}