LeetCode 力扣题目：买卖股票的最佳时机 III

❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容，和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣！

推荐：数据分析螺丝钉的首页格物致知终身学习期待您的关注

导航：

LeetCode解锁1000题: 打怪升级之旅：每题都包括3-5种算法，以及详细的代码实现，刷题面试跳槽必备
漫画版算法详解：通过漫画的形式和动态GIF图片把复杂的算法每一步进行详细可视解读，看一遍就掌握
python源码解读：解读python的源代码与调用关系，快速提升代码质量
python数据分析可视化：企业实战案例：企业级数据分析案例与可视化，提升数据分析思维和可视化能力
程序员必备的数学知识与应用：全面详细的介绍了工程师都必备的数学知识

期待与您一起探索技术、持续学习、一步步打怪升级欢迎订阅本专栏❤️❤️

题目描述

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

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

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

示例：

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

方法一：动态规划

解题步骤

定义状态：dp[i][j] 表示第 i 天完成 j 笔交易的最大利润。
初始化状态：dp[0][1] 和 dp[0][2] 都初始化为负无穷，表示不可能完成交易。
状态转移：
- 第 i 天完成一笔交易的最大利润：dp[i][1] = max(dp[i-1][1], -prices[i])
- 第 i 天完成两笔交易的最大利润：dp[i][2] = max(dp[i-1][2], dp[i-1][1] + prices[i])
结果输出：max(dp[n-1][1], dp[n-1][2])

Python 示例

def maxProfit(prices):
    n = len(prices)
    if n == 0:
        return 0
    dp = [[0] * 3 for _ in range(n)]
    dp[0][1] = -prices[0]
    dp[0][2] = float('-inf')
    
    for i in range(1, n):
        dp[i][1] = max(dp[i-1][1], -prices[i])
        dp[i][2] = max(dp[i-1][2], dp[i-1][1] + prices[i])

    return max(0, dp[n-1][2])

# Example usage
prices = [3,3,5,0,0,3,1,4]
print(maxProfit(prices))  # Output: 6

算法分析

时间复杂度：O(N)，其中 N 是数组的长度。
空间复杂度：O(N)，用于存储 dp 数组。

算法图解与说明

初始: dp = [[-3, -inf], [0, 0], [0, 0], ...]
第一天: 不操作，买入 -3
第二天: 不操作，维持 -3
第三天: 不操作，维持 -3
第四天: 不操作，买入 0
第五天: 不操作，维持 0
第六天: 卖出 +3
第七天: 买入 1
第八天: 卖出 +4

方法二：状态机优化

解题步骤

使用四个变量表示不同状态下的最大利润：buy1, sell1, buy2, sell2。
初始状态设为：buy1 = buy2 = -inf, sell1 = sell2 = 0。
更新状态机：
- buy1: 第一次买入的最大利润
- sell1: 第一次卖出的最大利润
- buy2: 第二次买入的最大利润
- sell2: 第二次卖出的最大利润

Python 示例

def maxProfit(prices):
    buy1, sell1, buy2, sell2 = float('-inf'), 0, float('-inf'), 0
    for price in prices:
        buy1 = max(buy1, -price)
        sell1 = max(sell1, buy1 + price)
        buy2 = max(buy2, sell1 - price)
        sell2 = max(sell2, buy2 + price)
    return sell2

# Example usage
prices = [3,3,5,0,0,3,1,4]
print(maxProfit(prices))  # Output: 6

算法分析

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

算法图解与说明

状态更新过程：
初始: buy1 = -inf, sell1 = 0, buy2 = -inf, sell2 = 0
价格迭代: 3 -> buy1 = -3
          3 -> sell1 = 0
          5 -> sell1 = 2
          0 -> buy2 = 2
          0 -> 维持
          3 -> sell2 = 5
          1 -> 维持
          4 -> sell2 = 6

这两种方法为买卖股票问题的高级解法，适用于有多次交易机会的场景。

方法三：左右扫描数组法

解题步骤

使用两个数组 left_profits 和 right_profits。left_profits[i] 存储从第一天到第 i 天的最大利润，right_profits[i] 存储从第 i 天到最后一天的最大利润。
从左到右遍历一遍股价数组，更新 left_profits 为到当前日为止的最大利润。
从右到左遍历股价数组，更新 right_profits 为从当前日到结束的最大利润。
最终结果为某一天两边利润之和的最大值。

Python 示例

def maxProfit(prices):
    n = len(prices)
    if n <= 1:
        return 0
    
    left_profits = [0] * n
    right_profits = [0] * n
    
    # 左侧最小值初始化
    min_price = prices[0]
    for i in range(1, n):
        left_profits[i] = max(left_profits[i-1], prices[i] - min_price)
        min_price = min(min_price, prices[i])
    
    # 右侧最大值初始化
    max_price = prices[n-1]
    for i in range(n-2, -1, -1):
        right_profits[i] = max(right_profits[i+1], max_price - prices[i])
        max_price = max(max_price, prices[i])
    
    # 计算两边利润的最大和
    max_profit = 0
    for i in range(n):
        max_profit = max(max_profit, left_profits[i] + right_profits[i])
    
    return max_profit

# Example usage
prices = [3,3,5,0,0,3,1,4]
print(maxProfit(prices))  # Output: 6

算法分析

时间复杂度：O(N)，其中 N 是数组的长度。
空间复杂度：O(N)，需要两个长度为 N 的数组来存储左右两侧的最大利润。

算法图解与说明

股票价格:  [3, 3, 5, 0, 0, 3, 1, 4]
左侧利润:  [0, 0, 2, 2, 2, 2, 2, 2]
右侧利润:  [3, 3, 3, 3, 3, 3, 3, 0]
最大利润:  每天两侧利润之和的最大值为 6 (第 6 天)

方法四：改进的状态机方法

解题步骤

减少状态机方法中变量的使用，只使用两个变量跟踪到目前为止的最大利润。
遍历价格数组时，更新四个关键状态：第一次买入、第一次卖出、第二次买入和第二次卖出的最大利润。
通过逐步更新这四个状态来最大化最终的利润。

Python 示例

def maxProfit(prices):
    first_buy, first_sell = float('-inf'), 0
    second_buy, second_sell = float('-inf'), 0
    for price in prices:
        first_buy = max(first_buy, -price)
        first_sell = max(first_sell, first_buy + price)
        second_buy = max(second_buy, first_sell - price)
        second_sell = max(second_sell, second_buy + price)
    return second_sell

# Example usage
prices = [3,3,5,0,0,3,1,4]
print(maxProfit(prices))  # Output: 6

算法分析

时间复杂度：O(N)，N 是股票价格数组的长度。
空间复杂度：O(1)，使用常数空间。

算法图解与说明

初始状态: first_buy = -inf, first_sell = 0, second_buy = -inf, second_sell = 0
更新过程:
- 第1天: first_buy 更新为 -3
- 第2天: 无变化
- 第3天: first_sell 更新为 2
- 第4天: second_buy 更新为 2
- 第5天: 无变化
- 第6天: second_sell 更新为 5
- 第7天: 无变化
- 第8天: second_sell 更新为 6

以上四种方法各有优势，适用于不同的场景和优化需求。可以根据具体需要选择最合适的解决方案。