买卖股票系列问题 Leetcode题目

今天药忘吃喽~ 2023-01-03 11:24 166阅读 0赞

# leetcode 刷题记录 #

## 一. 买卖股票系列问题 ##

### 1. [121. 买卖股票的最佳时机][121.] ###

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。  
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。  
注意：你不能在买入股票前卖出股票。  
**示例 1:**

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

**示例 2:**

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

**解法1：** 一次遍历

class Solution:
        def maxProfit(self, prices: List[int]) -> int:
            if len(prices) <= 1:
                return 0
            min_v = prices[0]  # 设置 股票最小值为初始值
            max_profile = 0  # 最大收益
            for i in range(1, len(prices)):
                if prices[i] < min_v:  # 小于 最小值时 可以尝试买入，此时没有收益
                    min_v = prices[i]
                else:    # 此时，大于最小值时，尝试卖出，但是 和 之前最大收益比较，
                    max_profile = max(prices[i] - min_v, max_profile)
            return max_profile

**解法2:** 动态规划, 感觉有点大材小用了

class Solution:
       def maxProfit(self, prices: List[int]) -> int:
           if len(prices) <= 1:
               return 0
           # dp[i]: 表示前i天的最大利润， dp[i]由前i-1天的最大利润 和 第i天的利润 决定的， 
           # 递推公式: dp[i] = max(dp[i-1], prices[i] - minprices) # minprices表示之前的 最低价格
           # 这题使用 动态规划，大材小用了
           len_prices = len(prices)
           dp = [0] * len_prices
           dp[0] = 0 
           minprices = prices[0]
           for i in range(1, len_prices):
               minprices = min(minprices, prices[i])
               dp[i] = max(dp[i-1], prices[i] - minprices)  # 比方法1麻烦了
           return dp[-1]

**解法3:** 暴力 思路很简单就是， 计算当前价格和之前最低价格的差值，找到最大值； 3692 ms

class Solution:
        def maxProfit(self, prices: List[int]) -> int:
            if len(prices) <= 1:
                return 0
            dp = [0] * len(prices)
            for i in range(len(prices)-1, 0, -1): 
                temp = prices[i] - min(prices[:i])  # 计算当前和 之前最低价格 最小值
                dp[i] = temp if temp > 0 else 0
            return max(dp)

### [122. 买卖股票的最佳时机 II][122. _ II] ###

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

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

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

**解法1：** 动态规划

class Solution:
        def maxProfit(self, prices: List[int]) -> int:
            if len(prices) <= 1:
                return 0
            len_prices = len(prices)
            dp = [0] * len_prices
            dp[0] = 0
            # dp[i]:表示第i天收益
            min_prices = prices[0]
            for i in range(1, len_prices):  # 什么时候售掉?
                min_prices = min(min_prices, prices[i])
                if i < len_prices - 1 and  min_prices < prices[i] and prices[i] > prices[i+1]:
                    dp[i] = (prices[i] - min_prices)
                    min_prices = prices[i+1]
                elif i == len_prices -1:
                    dp[i] = (prices[i] - min_prices)
            return sum(dp)

或者 不使用动态规划，一次遍历，

class Solution:
        def maxProfit(self, prices: List[int]) -> int:
            if len(prices) <= 1:
                return 0
            len_prices = len(prices)
            sum_price = 0   # 最终利润
            min_prices = prices[0]
            for i in range(1, len_prices):  # 什么时候售掉? 判断条件太复杂，
                min_prices = min(min_prices, prices[i])
                if i < len_prices - 1 and  min_prices < prices[i] and prices[i] > prices[i+1]:
                    sum_price += (prices[i] - min_prices)
                    min_prices = prices[i+1]
                elif i == len_prices -1:
                    sum_price += (prices[i] - min_prices)
            return sum_price

**解法2：** 贪心法， 不太好理解 参考[官方][Link 1]  
最大化公式 ∑ i = 1 x a \[ r i \] − a \[ l i \] \\sum\_\{i=1\}^\{x\} a\[r\_i\] - a\[l\_i\] i=1∑xa\[ri\]−a\[li\]  
其实等价于 连续若干个长度为1的区间价值和。

class Solution:
        def maxProfit(self, prices: List[int]) -> int:
            if len(prices) <= 1:
                return 0
            # 贪心法
            max_profile = 0
            for i in range(1, len(prices)):
                max_profile += max(0, prices[i]-prices[i-1])
            return max_profile

**解法3** 动态规划

class Solution:
        def maxProfit(self, prices: List[int]) -> int:
            if len(prices) <= 1:
                return 0
            # 动态规划
            # dp[i][0]: 表示第i天交易完后，手里没有股票的最大利润；
            # 状态转移方程： dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i]); 可能之前没有股票，或 有股票 现在卖了；
            # dp[i][1]: 表示第i天交易完后，手里持有一支股票的最大利润； 持有股票，数值是负的
            # 状态转移方程： dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i]); 可能之前就有股票， 或 之前没有股票，现在买入股票（买入股票 减）；
            len_prices = len(prices)
            dp = [[0, 0] for i in range(len_prices)]
            dp[0][0] = 0
            dp[0][1] = -prices[0]
            for i in range(1, len_prices):
                dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
                dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])
            
            return dp[len_prices-1][0]

### [309. 最佳买卖股票时机含冷冻期][309.] ###

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

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

*  卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

**解法1:** 动态规划, 仔细琢磨， 反复记忆

class Solution:
        def maxProfit(self, prices: List[int]) -> int:
            # 多了个 冷冻期
            # 设置三个状态
            if len(prices) <= 1:
                return 0 
            len_prices = len(prices)
            dp = [[0, 0, 0] for i in range(len_prices)]
            # dp[i][0]: 手上持有股票的最大收益
            # dp[i][1]: 手上不持有股票，并且处于冷冻期的 累计最大收益
            # dp[i][2]: 手上不持有股票，并且不处于冷冻期中的 最大收益
            dp[0][0] = -prices[0]
            dp[0][1] = 0
            dp[0][2] = 0
            for i in range(1, len_prices):
                dp[i][0] = max(dp[i-1][0], dp[i-1][2]-prices[i]) # i-1不处于冷冻可以买
                dp[i][1] = dp[i-1][0] + prices[i]
                dp[i][2] = max(dp[i-1][1], dp[i-1][2]) # 之前处于冷冻期， 或者 之前不处于冷冻期
            return max(dp[len_prices-1][1], dp[len_prices-1][2])

### [714. 买卖股票的最佳时机含手续费][714.] ###

### [123. 买卖股票的最佳时机 III][123. _ III] ###

### [188. 买卖股票的最佳时机 IV][714.] ###

[121.]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
[122. _ II]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
[Link 1]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/solution/mai-mai-gu-piao-de-zui-jia-shi-ji-ii-by-leetcode-s/
[309.]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
[714.]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
[123. _ III]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/