LeetCode 力扣题目:买卖股票的最佳时机 IV

简介: LeetCode 力扣题目:买卖股票的最佳时机 IV

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

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

买卖股票的问题在力扣(LeetCode)上是一个系列,涵盖了从简单到困难的多种变体,每个题目都有其特定的条件和限制。这里是一些常见题目的主要区别:

  1. 买卖股票的最佳时机121题
  • 条件:只允许完成一笔交易(即买入和卖出一次股票)。
  • 目标:求最大利润。
  1. 买卖股票的最佳时机 II 122题
  • 条件:可以进行多次交易,但必须在再次购买前出售掉之前的股票。
  • 目标:求最大利润。
  1. 买卖股票的最佳时机 III 123题
  • 条件:最多可以完成两笔交易。
  • 目标:求最大利润。

题目描述

给定一个整数数组 prices,其表示一支股票的价格变化;再给定一个整数 k,表示你最多可以完成 k 笔交易(买入和卖出算一笔交易,且每次交易之前必须卖出手中的股票)。请求出你能够获得的最大利润。

注意: 你不能同时参与多笔交易(必须在再次购买前卖掉之前的股票)。

示例:

输入: k = 2, prices = [2,4,1]

输出: 2

解释: 在第1天(价格 = 2)的时候买入,在第2天(价格 = 4)的时候卖出,这笔交易所能获得利润 = 4-2 = 2。

方法一:动态规划

解题步骤

  1. 定义状态 dp[i][j] 表示第 i 天结束时,进行了 j 次交易的最大利润。
  2. 对于每天的股票价格,更新买入和卖出状态:
  • dp[i][j] 可以由 dp[i-1][j](不操作)或 dp[i-1][j-1] - prices[i](买入)更新。
  • dp[i][j] 也可以通过 dp[i-1][j-1] + prices[i](卖出)更新。
  1. 初始化状态,dp[0][...] = 0 或根据第一天的操作调整。
  2. 遍历完成后,dp[n-1][k] 为最大利润。

Python 示例

def maxProfit(k, prices):
    n = len(prices)
    if n < 2:
        return 0
    if k >= n // 2:
        return sum(x - y for x, y in zip(prices[1:], prices[:-1]) if x > y)
    dp = [[0] * (k + 1) for _ in range(n)]
    for j in range(1, k + 1):
        max_buy = -prices[0]
        for i in range(1, n):
            dp[i][j] = max(dp[i - 1][j], prices[i] + max_buy)
            max_buy = max(max_buy, dp[i - 1][j - 1] - prices[i])
    return dp[-1][k]
# Example usage
k = 2
prices = [2, 4, 1]
print(maxProfit(k, prices))  # Output: 2

算法分析

  • 时间复杂度:O(n*k),其中 n 是数组的长度。
  • 空间复杂度:O(n*k),用于存储 dp 数组。

算法图解与说明

初始: dp = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
第一天: 不操作或买入
第二天: 卖出或继续持有
第三天: 选择最优操作

方法二:优化空间的动态规划

解题步骤

  1. 使用滚动数组优化空间复杂度,仅使用两行来存储当前和前一天的状态。
  2. 同样遵循动态规划的状态转移方程,但在每天结束后,将当前天的状态复制到“前一天”数组中。
  3. 通过优化状态转移的方式,减少空间使用,确保算法更高效。

Python 示例

def maxProfit(k, prices):
    n = len(prices)
    if n < 2:
        return 0
    if k >= n // 2:
        return sum(max(prices[i + 1] - prices[i], 0) for i in range(n - 1))
    
    dp = [[0] * (k + 1) for _ in range(2)]
    for j in range(1, k + 1):
        max_buy = -prices[0]
        for i in range(1, n):
            dp[i % 2][j] = max(dp[(i - 1) % 2][j], prices[i] + max_buy)
            max_buy = max(max_buy, dp[(i - 1) % 2][j - 1] - prices[i])
    return dp[(n - 1) % 2][k]
# Example usage
k = 2
prices = [2, 4, 1]
print(maxProfit(k, prices))  # Output: 2

算法分析

  • 时间复杂度: O(n*k),其中 n 是股票价格的天数。
  • 空间复杂度: O(k),因为我们只保持了两个长度为 k+1 的数组。

算法图解与说明

假设 k=2, prices=[2, 4, 1]
使用滚动数组优化:
初始: dp[0][...] = [0, 0, 0]
      dp[1][...] = [0, 0, 0]
第1天: max_buy = -2
第2天: dp[1][1] = max(dp[0][1], 4 - 2)
       dp[1][2] = max(dp[0][2], dp[0][1] - 2)
继续更新...

方法三:局部最优与全局最优解法

解题步骤

  1. 使用两个数组 localglobal 来存储局部最优和全局最优的利润。
  2. local[i][j] 表示到达第 i 天时最多进行 j 次交易,并且最后一次交易在第 i 天卖出的最大利润。
  3. global[i][j] 表示到达第 i 天时最多进行 j 次交易的最大利润。
  4. 更新规则:
  • local[i][j] = max(global[i-1][j-1] + max(0, prices[i] - prices[i-1]), local[i-1][j] + (prices[i] - prices[i-1]))
  • global[i][j] = max(global[i-1][j], local[i][j])

Python 示例

def maxProfit(k, prices):
    n = len(prices)
    if n < 2 or k <= 0:
        return 0
    if k >= n // 2:
        return sum(max(prices[i + 1] - prices[i], 0) for i in range(n - 1))
    
    local = [[0] * (k + 1) for _ in range(n)]
    global_profit = [[0] * (k + 1) for _ in range(n)]
    for i in range(1, n):
        delta = prices[i] - prices[i - 1]
        for j in range(1, k + 1):
            local[i][j] = max(global_profit[i-1][j-1] + max(delta, 0), local[i-1][j] + delta)
            global_profit[i][j] = max(global_profit[i-1][j], local[i][j])
    
    return global_profit[-1][k]
# Example usage
k = 2
prices = [2, 4, 1]
print(maxProfit(k, prices))  # Output: 2

算法分析

  • 时间复杂度: O(n*k),每天的每个交易次数都进行了计算。
  • 空间复杂度: O(n*k),存储局部和全局最优利润。

算法图解与说明

股票价格:  [2, 4, 1]
local 和 global 更新:
第2天 (价格4): local[1][1] = max(global[0][0] + 2, 0) = 2
              global[1][1] = max(global[0][1], local[1][1]) = 2
继续追踪并更新所有局部和全局最优解...

这些方法提供了不同的策略来处理买卖股票的最佳时机问题,特别是当交易次数有限制时。每种方法都有其适用场景和优缺点,可以根据具体需求和资源情况选择最合适的策略。

🌹🌹如果觉得这篇文对你有帮助的话,记得一键三连关注、赞👍🏻、收藏是对作者最大的鼓励,非常感谢 ❥(^_-)

❤️❤️作者知识有限,如有错误,请各位大佬评论区批评指正,不胜感激❥(^_-)

欢迎关注微信公众号 数据分析螺丝钉

相关文章
|
3月前
|
算法 Python
【Leetcode刷题Python】309. 最佳买卖股票时机含冷冻期
解决LeetCode上309题“最佳买卖股票时机含冷冻期”的Python代码示例,利用动态规划方法计算在含有冷冻期约束下的最大利润。
40 1
|
18天前
|
程序员 C语言
【C语言】LeetCode(力扣)上经典题目
【C语言】LeetCode(力扣)上经典题目
|
21天前
|
索引
力扣(LeetCode)数据结构练习题(3)------链表
力扣(LeetCode)数据结构练习题(3)------链表
53 0
|
21天前
力扣(LeetCode)数据结构练习题(2)
力扣(LeetCode)数据结构练习题(2)
25 0
|
21天前
|
存储
力扣(LeetCode)数据结构练习题
力扣(LeetCode)数据结构练习题
39 0
|
3月前
|
算法
leetcode188 买卖股票的最佳时机IV
leetcode188 买卖股票的最佳时机IV
60 0
|
3月前
|
算法 Python
【Leetcode刷题Python】714. 买卖股票的最佳时机含手续费
提供了两种解决买卖股票最佳时机含手续费问题的Python实现方法:贪心算法和动态规划算法。
41 0
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
52 6
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
102 2