likes
comments
collection
share

买卖股票问题汇总📈

作者站长头像
站长
· 阅读数 4

在LeetCode上，有多个与📈股票交易相关的问题，这些问题通常涉及在给定的股价列表中选择合适的时间点进行买入和卖出，以获得最大的利润。

  1. 买卖股票的最佳时机 (Best Time to Buy and Sell Stock):

    这是最基本的股票交易问题。给定一个股价数组，你只能完成一次交易（即买一次股票和卖一次股票），求最大利润。

  2. 买卖股票的最佳时机 II (Best Time to Buy and Sell Stock II):

    类似于第一个问题，但是这次你可以进行多次交易。→ 你可以在同一天卖出股票并再次购买。

  3. 买卖股票的最佳时机 III (Best Time to Buy and Sell Stock III):

    允许最多完成两笔交易，求最大利润。

  4. 买卖股票的最佳时机 IV (Best Time to Buy and Sell Stock IV):

    允许最多完成 k 笔交易，求最大利润。这个问题通常使用动态规划来解决。

  5. 买卖股票的最佳时机含手续费 (Best Time to Buy and Sell Stock with Transaction Fee):

    和第二个问题类似，但在卖出股票时需要支付交易费用。

这些问题的难度逐渐增加，要求更多的交易次数或者包含更多的交易规则。解决这些问题通常可以使用动态规划、贪心算法等技巧。 今天我们就说一下前三道难度没那么大的题目。 

🙂搭配我写的思路分析以及代码分析食用更佳！

121. 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入： [7,1,5,3,6,4]
输出： 5
解释： 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

输入： prices = [7,6,4,3,1]
输出： 0
解释： 在这种情况下, 没有交易完成, 所以最大利润为 0。

 

提示：

  • 1<=prices.length<=1051 <= prices.length <= 10^51<=prices.length<=105
  • 0<=prices[i]<=1040 <= prices[i] <= 10^40<=prices[i]<=104

分析

profit表示当前所能获得的最大收益。

设定一个值记录历史最低点，之后的每一步计算都是假设在历史最低点买入。

所以整个递推过程为：

profit[i]=max(profit[i−1],prices[i]−minprofit)profit[i] = max(profit[i-1],prices[i]-minprofit)profit[i]=max(profit[i−1],prices[i]−minprofit)

profit[0]的初始化：

题目要求只能在未来的某一天卖出，所以不能当天买了当天卖。

所以我在第一天买入，第一天的利润讲道理应该是 -prices[0]。

profit[i]=max(profit[i−1],prices[i]−minprofit)profit[i] = max(profit[i-1],prices[i]-minprofit)profit[i]=max(profit[i−1],prices[i]−minprofit)表示的就是我在今天卖出的利润和我之前的最大利润作比较。

这样的话profit保证存储的一定是最大的利润。但是韭菜人韭菜魂，可能到最后最大利润也是负数，所以最后返回值要确认一下最大利润是不是负数，如果是负数就返回0。

但是如果直接初始化为0，后续计算的逻辑就相当于，第一天一定不买！--> 如果当前买了会赔本，那就直接不买了，将当前利润设置为0。有那么点未卜先知的意思，就是我要知道之后的某天价格比今天高，我再回来买今天的😂。

代码

  • 初始化profit = -prices[0]

    class Solution:
    def maxProfit(self, prices) -> int:
        profit = [0] * len(prices)
        profit[0] = -prices[0]
        minPrice = prices[0]
        for i in range(1, len(prices)):
            profit[i] = max(prices[i] - minPrice, profit[i - 1])
            minPrice = min(minPrice, prices[i])
        return profit[-1] if profit[-1] >= 0 else 0

  • 初始化profit = 0

    class Solution:
    def maxProfit(self, prices) -> int:
        profit = [0] * len(prices)
        minPrice = prices[0]
        for i in range(1, len(prices)):
            profit[i] = max(prices[i] - minPrice, profit[i - 1])
            minPrice = min(minPrice, prices[i])   # 记得更新一下历史最低价
        return profit[-1]

    空间优化：

    class Solution:
    def maxProfit(self, prices) -> int:
        # 空间优化
        minprice = float('inf')
        maxprofit = 0
        for price in prices:
            maxprofit = max(maxprofit, price - minprice)
            minprice = min(minprice, price)
        return maxprofit

    第一段代码：

    该算法使用动态规划的思想，它需要维护一个列表profit，记录每天的最大收益。该算法遍历价格列表，并计算以每个价格为卖出价格时的最大利润，最终返回profit列表中的最后一个元素。

    该算法的时间复杂度为O(n)，空间复杂度也为O(n)，其中n为价格列表的长度。

    第二段代码：

    该算法与第一段代码相似，但是它使用两个变量minprice和maxprofit来分别记录历史最低价和最大收益。它遍历价格列表，计算每个价格与历史最低价之间的差值，并更新历史最低价和最大收益。

    该算法的时间复杂度为O(n)，空间复杂度为O(1)，其中n为价格列表的长度。

122. 买卖股票的最佳时机 II

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

 

示例 1：

输入： prices = [7,1,5,3,6,4]
输出： 7
解释： 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
     总利润为 4 + 3 = 7 。

示例 2：

输入： prices = [1,2,3,4,5]
输出： 4
解释： 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     总利润为 4 。

示例 3：

输入： prices = [7,6,4,3,1]
输出： 0
解释： 在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。

 

提示：

  • 1<=prices.length<=3∗1041 <= prices.length <= 3 * 10^41<=prices.length<=3∗104

  • 0<=prices[i]<=1040 <= prices[i] <= 10^40<=prices[i]<=104

分析

这题和上一题的区别在于：

  • 当天买了可以当天卖。

  • 可以买卖多次。

所以第一天的时候，最大利润肯定是0，这里profit[0]初始化就不用考虑别的了。

之后的递推关系：

profit[i]=max(profit[i−1],profit[i−1]+prices[i]−prices[i−1])profit[i] = max(profit[i-1],profit[i-1] + prices[i] - prices[i-1])profit[i]=max(profit[i−1],profit[i−1]+prices[i]−prices[i−1])

我之前的利润，加上昨天买入今天卖出的利润，取最大值，也就是假设每次都是前一天买入第二天卖出。

代码

  • DP

    class Solution:
    def maxProfit(self, prices: [int]) -> int:
        profit = [0] * len(prices)
        for i in range(1, len(prices)):
            profit[i] = max(profit[i - 1], prices[i] - prices[i - 1] + profit[i - 1])
        return profit[-1]

    空间优化

    class Solution:
    def maxProfit(self, prices: [int]) -> int:
        profit = 0
        for i in range(1, len(prices)):
            profit = max(profit, prices[i] - prices[i - 1] + profit)
        return profit

  • 贪心

    上边那个思路完全基于贪心算法，所以直接写贪心吧，不装了。

    class Solution:
    def maxProfit(self, prices: [int]) -> int:
        # 貪心
        profit = 0
        for i in range(1, len(prices)):
            if prices[i] > prices[i - 1]:
                profit += prices[i] - prices[i - 1]
        return profit

    这段代码采用了贪心算法的思想，即只要当前价格比前一天高，就在前一天买进，今天卖出，以此获得最大的利润。具体来说，从第2天开始遍历prices数组，如果当天价格比前一天价格高，则计算这两天之间的差价并将其加入到profit中。

    这种贪心算法的时间复杂度为O(n)，空间复杂度为O(1)，其中n为prices数组的长度。相比之下，动态规划算法的时间复杂度为O(n)，空间复杂度为O(n)。贪心算法在该问题上的表现更好，因为它只需要一次遍历即可得到最优解。

123. 买卖股票的最佳时机 III

给定一个数组，它的第i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意： 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

 

示例 1:

输入： prices = [3,3,5,0,0,3,1,4]
输出： 6
解释： 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
     随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

示例 2：

输入： prices = [1,2,3,4,5]
输出： 4
解释： 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。   
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3：

输入： prices = [7,6,4,3,1] 
输出： 0 
解释： 在这个情况下, 没有交易完成, 所以最大利润为 0。

示例 4：

输入： prices = [1]
输出： 0

 

提示：

  • 1<= prices.length<=1051 <= prices.length <= 10^51<= prices.length<=105
  • 0<= prices[i]<= 1050 <= prices[i] <= 10^50<= prices[i]<= 105

代码

  • DP

    class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        p1b, p1s, p2b, p2s = -prices[0], 0, -prices[0], 0
        for price in prices[1:]:
            p1b = max(p1b, -price)
            p1s = max(p1s, p1b + price)
            p2b = max(p2b, p1s - price)
            p2s = max(p2s, p2b + price)
        return p2s

    p1b 表示第一次买入股票后的最大利润（负数表示花费了多少钱买入股票），p1s 表示第一次卖出股票后的最大利润。这两个变量的更新是基于第一次交易的情况。

    p2b 表示第二次买入股票后的最大利润，p2s 表示第二次卖出股票后的最大利润。这两个变量的更新是基于第一次和第二次交易的情况。

    算法遍历输入的股价列表，从第二个股价开始，依次更新这四个变量的值。对于每个股价，算法更新这些变量的策略如下：

    • 如果第一次买入股票后的剩余利润小于当前股价的负数（即花费更少的钱买入当前股票），则更新 p1b。
    • 如果第一次卖出股票后的剩余利润小于第一次买入股票后的剩余利润加上当前股价，则更新 p1s。
    • 如果第二次买入股票后的剩余利润小于第一次卖出股票后的剩余利润减去当前股价（即如果第二次买入股票能够使利润增加），则更新 p2b。
    • 如果第二次卖出股票后的剩余利润小于第二次买入股票后的剩余利润加上当前股价，则更新 p2s。

    最终，返回 p2s，它代表了完成两笔交易后的最大利润。

    算法遍历输入的股价列表一次，所以时间复杂度是 O(n)，其中 n 是股价列表的长度。算法使用了常数级别的额外空间来存储四个变量，因此空间复杂度是 O(1)。