❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容,和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣!
- 推荐:数据分析螺丝钉的首页 格物致知 终身学习 期待您的关注
- 导航:
- LeetCode解锁1000题: 打怪升级之旅:每题都包括3-5种算法,以及详细的代码实现,刷题面试跳槽必备
- 漫画版算法详解:通过漫画的形式和动态GIF图片把复杂的算法每一步进行详细可视解读,看一遍就掌握
- python源码解读:解读python的源代码与调用关系,快速提升代码质量
- python数据分析可视化:企业实战案例:企业级数据分析案例与可视化,提升数据分析思维和可视化能力
- 程序员必备的数学知识与应用:全面详细的介绍了工程师都必备的数学知识
期待与您一起探索技术、持续学习、一步步打怪升级 欢迎订阅本专栏❤️❤️
买卖股票的问题在力扣(LeetCode)上是一个系列,涵盖了从简单到困难的多种变体,每个题目都有其特定的条件和限制。这里是一些常见题目的主要区别:
- 买卖股票的最佳时机121题
- 条件:只允许完成一笔交易(即买入和卖出一次股票)。
- 目标:求最大利润。
- 买卖股票的最佳时机 II 122题
- 条件:可以进行多次交易,但必须在再次购买前出售掉之前的股票。
- 目标:求最大利润。
- 买卖股票的最佳时机 III 123题
- 条件:最多可以完成两笔交易。
- 目标:求最大利润。
题目描述
给定一个整数数组 prices
,其表示一支股票的价格变化;再给定一个整数 k
,表示你最多可以完成 k
笔交易(买入和卖出算一笔交易,且每次交易之前必须卖出手中的股票)。请求出你能够获得的最大利润。
注意: 你不能同时参与多笔交易(必须在再次购买前卖掉之前的股票)。
示例:
输入: k = 2
, prices = [2,4,1]
输出: 2
解释: 在第1天(价格 = 2)的时候买入,在第2天(价格 = 4)的时候卖出,这笔交易所能获得利润 = 4-2 = 2。
方法一:动态规划
解题步骤
- 定义状态
dp[i][j]
表示第i
天结束时,进行了j
次交易的最大利润。 - 对于每天的股票价格,更新买入和卖出状态:
dp[i][j]
可以由dp[i-1][j]
(不操作)或dp[i-1][j-1] - prices[i]
(买入)更新。dp[i][j]
也可以通过dp[i-1][j-1] + prices[i]
(卖出)更新。
- 初始化状态,
dp[0][...] = 0
或根据第一天的操作调整。 - 遍历完成后,
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]] 第一天: 不操作或买入 第二天: 卖出或继续持有 第三天: 选择最优操作
方法二:优化空间的动态规划
解题步骤
- 使用滚动数组优化空间复杂度,仅使用两行来存储当前和前一天的状态。
- 同样遵循动态规划的状态转移方程,但在每天结束后,将当前天的状态复制到“前一天”数组中。
- 通过优化状态转移的方式,减少空间使用,确保算法更高效。
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) 继续更新...
方法三:局部最优与全局最优解法
解题步骤
- 使用两个数组
local
和global
来存储局部最优和全局最优的利润。 local[i][j]
表示到达第 i 天时最多进行 j 次交易,并且最后一次交易在第 i 天卖出的最大利润。global[i][j]
表示到达第 i 天时最多进行 j 次交易的最大利润。- 更新规则:
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 继续追踪并更新所有局部和全局最优解...
这些方法提供了不同的策略来处理买卖股票的最佳时机问题,特别是当交易次数有限制时。每种方法都有其适用场景和优缺点,可以根据具体需求和资源情况选择最合适的策略。
🌹🌹如果觉得这篇文对你有帮助的话,记得一键三连关注、赞👍🏻、收藏是对作者最大的鼓励,非常感谢 ❥(^_-)
❤️❤️作者知识有限,如有错误,请各位大佬评论区批评指正,不胜感激❥(^_-)
欢迎关注微信公众号 数据分析螺丝钉