leetcode刷题笔记——股票交易问题总结

置顶 Ckyeka

已于 2024-03-31 22:38:40 修改

阅读量1.1k

点赞数 8

分类专栏：算法文章标签： leetcode 算法 python

于 2024-03-28 18:49:17 首次发布

本文链接：https://blog.csdn.net/Shallowmm/article/details/137120878

版权

算法专栏收录该内容

4 篇文章

订阅专栏

股票交易问题

1. 限制单次交易

121. Best Time to Buy and Sell Stock

问题描述：

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example：

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

从题干中可以得知，我们只能进行一次交易并且购买和卖出不能在同一天，因此只需要找到全局股价最低点和最高点，二者的差就是答案

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)

        if n <= 1:
            return 0

        min_price = prices[0]
        max_profit = 0
        for i in range(1, n):
            max_profit = max(max_profit, prices[i] - min_price)
            if prices[i] < min_price:
                min_price = prices[i]

        return max_profit

2. 无限制交易

122. Best Time to Buy and Sell Stock II

问题描述：

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

Example：

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.

由于不限制交易次数并且买入和卖出可以是同一天，因此只要第i天的股价高于前一天，我们就选择交易

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

3. 带限制的交易

3.1 限制交易次数

123. Best Time to Buy and Sell Stock III

188. Best Time to Buy and Sell Stock IV

假如限制只能进行k次交易，又该如何解决？下面以Leetcode 188为例

问题描述：

You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k.

Find the maximum profit you can achieve. You may complete at most k transactions: i.e. you may buy at most k times and sell at most k times.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example：

Input: k = 2, prices = [3,2,6,5,0,3]
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

首先，分类讨论k的取值情况

当k $\ge$ n时，每一天我们都可以进行一次交易，相当于不限制交易，直接套用Leetcode 122的做法，有收益就交易
当k $\lt$ n时，我们需要选择收益最高的k次交易，考虑采用dp解决，声明两个dp数组buy和sell分别表示第i次购买/卖出时所取得的最大收益，状态转移方程如下，注意我们对dp数组进行了空间压缩，省略了天数这一维度
- buy[i] = max(buy[i], sell[i - 1] - prices[i])
- sell[i] = max(sell[i], buy[i] + prices[i])

代码实现如下：

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)

        if n <= 1:
            return 0

        if k < n:
            # 选择全局最优的k次交易
            sell = [0 for i in range(k + 1)]  # 第k次卖出时的最大收益
            buy = [-1e7 for i in range(k + 1)]  # 第k次买入时的最大收益
            for i in range(n):
                for j in range(1, k + 1):
                    buy[j] = max(buy[j], sell[j - 1] - prices[i])
                    sell[j] = max(sell[j], buy[j] + prices[i])

            return sell[k]
        else:
            # 只要有收益就卖
            max_profits = 0
            for i in range(1, n):
                if prices[i] > prices[i - 1]:
                  max_profits += (prices[i] - prices[i - 1])
            return max_profits

3.2 带冷却时间的交易

309. Best Time to Buy and Sell Stock with Cooldown

每次卖出股票后必须隔一天才能再买入股票

问题描述：

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions:

After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example：

Input: prices = [1,2,3,0,2]
Output: 3
Explanation: transactions = [buy, sell, cooldown, buy, sell]

股票购买问题本质上就是一个有限状态机，对于这类问题，画出状态转换图即可解之

s0表示待买入阶段，买入第i天的股票后转移到buy状态，也可以选择不购买重复等待

在进入buy状态后可以直接卖掉股票转移到sell状态也可以选择转移到imm状态重复等待

由于卖出股票后有一天的冷却时间，所以在卖出股票后先转移到sell状态，后一天才可以重新回到s0状态

对于每一种状态：

如果存在自己指向自己的箭头，那么就用当前状态的前一天状态进行更新
如果存在其他状态指向该状态，那么就用其他状态的前一天状态进行更新
当出现多个状态指向该状态时，取最大值

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        if n <= 1:
            return 0

        buy = [0 for i in range(n)]
        sell = [0 for i in range(n)]
        s1 = [0 for i in range(n)]
        s2 = [0 for i in range(n)]
        buy[0] = -prices[0]
        s2[0] = -prices[0]

        for i in range(1, n):
            buy[i] = s1[i - 1] - prices[i]
            s2[i] = max(s2[i - 1], buy[i - 1])
            sell[i] = max(buy[i - 1], s2[i - 1]) + prices[i]
            s1[i] = max(s1[i - 1], sell[i - 1])

        return max(s1[n - 1], sell[n - 1])