Leetcode股票买卖6题分析

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
}

  Reprint please specify: KYLE LIU Leetcode股票买卖6题分析

 Previous
【转】深度解密Go语言之Slice 【转】深度解密Go语言之Slice
这是你自定义的文章摘要内容,如果这个属性有值,文章卡片摘要就显示这段文字,否则程序会自动截取文章的部分内容作为摘要
2019-04-01
Next 
Oracle11GR2 RAC DataGuard容灾实施与维护手册 Oracle11GR2 RAC DataGuard容灾实施与维护手册
这是你自定义的文章摘要内容,如果这个属性有值,文章卡片摘要就显示这段文字,否则程序会自动截取文章的部分内容作为摘要
2018-10-07
  TOC