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
}