121 Best Time to Buy and Sell Stock

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

solution

• 只能进行一笔买卖交易

• 贪心

# 一次迭代过程，只记录之前出现的最低值，也计算目前出现的最大利润。两种计算非同时触发
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        low = float('inf')
        profit = 0
        for price in prices:
            if price < low:  # 可转化为 low = min(low, i), 截止到目前遇到的最低价格
                low = price
            if price - low > profit:  # 可转化为 profit = max(profit, i - low), 截止目前的最大利润
                profit = price - low
        return profit        

时间复杂度：O(n) 空间复杂度：O(1)

• 动态规划

  • dp含义很关键，注意dp[i][0]和dp[i][1]分布是持有和不持有股票，手里最多现金。持有可以是原来就持有，也可以是当天才买。不持有可以是一直不持有，可以是当天才卖。

  • 初始可以认为现金是0，可以初始假设了某笔钱，最后也需要减掉。然后，中间如果有亏损，本身也是负的现金

# 只和过去一个时间有关的, 空间可以优化
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp = [[0] * 2 for _ in range(len(prices))]

        dp[0][0] = -prices[0]
        dp[0][1] = 0

        for i in range(1, len(prices)):
            dp[i][0] = max(dp[i-1][0], -prices[i])  # 只进行一笔，所以买之后利润肯定是-当前价格
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])
        
        return dp[-1][1]

时间复杂度：O(n) 空间复杂度：O(n)

follow up-股票买卖类

122. Best Time to Buy and Sell Stock II

• 可以进行无数笔交易，注意先买后卖

• 递增区间的和

• dp含义不变，只是公式有更新

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp = [[0] * 2 for _ in range(len(prices))]
        dp[0][0] = -prices[0]
        dp[0][1] = 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[-1][1]

时间复杂度：O(n) 空间复杂度：O(n)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        res = 0
        for i in range(1, len(prices)):
            if prices[i] >= prices[i-1]:  # 递增区间
                res = res + prices[i] - prices[i-1]  # 和
            else:
                continue
        return res

123. Best Time to Buy and Sell Stock III

• 最多完成两笔交易

• dp含义差不多？类似问题中，二维dp中的第二维是某种状态枚举

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) <= 1:
            return 0
        
        dp = [[0] * 4 for _ in range(len(prices))]
        dp[0][0] = -prices[0]
        dp[0][2] = -prices[0]  # 注意第二次持有的初始化

        for i in range(1, len(prices)):
            dp[i][0] = max(dp[i-1][0], -prices[i])  # 注意和前几天的比较
            dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i])
            dp[i][2] = max(dp[i-1][2], dp[i-1][1]-prices[i])
            dp[i][3] = max(dp[i-1][3], dp[i-1][2]+prices[i])
        return max(dp[-1][1], dp[-1][3])

时间复杂度：O(n) 空间复杂度：O(n), 可继续优化至O(1)

188. Best Time to Buy and Sell Stock IV

• 最多完成k笔交易

• 把最多完成两笔交易中的2进一步参数化

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        if len(prices) <= 1:
            return 0
        
        dp = [[0] * (2 * k + 1) for _ in range(len(prices))]
        for j in range(1, 2 * k, 2):
            dp[0][j] = -prices[0]  # 同样注意所有奇数次持有的初始化
        
        for i in range(1, len(prices)):
            for j in range(0, 2 * k - 1, 2):
                dp[i][j+1] = max(dp[i-1][j+1], dp[i-1][j]-prices[i])
                dp[i][j+2] = max(dp[i-1][j+2], dp[i-1][j+1]+prices[i])
        return dp[-1][2*k]

时间复杂度：O(n) 空间复杂度：O()

309. Best Time to Buy and Sell Stock with Cooldown

• 含冷冻期

• 注意状态划分与转移，仍然是第二维是状态

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) <= 1:
            return 0
        
        dp = [[0] * 4 for _ in range(len(prices))]
        dp[0][0] = -prices[0]

        for i in range(1, len(prices)):
            dp[i][0] = max(dp[i-1][0], dp[i-1][2]-prices[i])  # hold, 之前持有或非冷冻期买入
            dp[i][1] = dp[i-1][0] + prices[i]  # sell, 前一天持有后卖出，卖出后进入的是冷冻状态，因此没有dp[i-1][1]     
            dp[i][2] = max(dp[i-1][2], dp[i-1][1])  # cool, 注意该状态是冷冻或冷冻期之后可买入的状态， 因此还要和自己过去比较
        return max(dp[-1][1], dp[-1][2])

时间复杂度：O(n) 空间复杂度：O()

714. Best Time to Buy and Sell Stock with Transaction Fee

• 含交易手续费

• 和122类似，卖出时加上手续费

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        if len(prices) <= 1:
            return 0
        
        dp = [[0] * 2 for _ in range(len(prices))]
        dp[0][0] = -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]-fee)
        return dp[-1][1]

时间复杂度：O(n) 空间复杂度：O()