示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本文以 doocs/leetcode 仓库中 0122.Best Time to Buy and Sell Stock II 的题解为主体系统讲解可无限次交易、最多持有一股场景下的最大利润求解先给出直观的贪心结论与正确性直觉再推导可推广到冷冻期、手续费等变体的动态规划状态机模型最后给出空间优化的滚动变量写法并附 Python、Java、C、Go、TypeScript、Rust、JavaScript、C# 八种语言的完整可运行代码。读完本文你将同时掌握逐日累加正差价的 O(n) 贪心写法以及一套能迁移到 0123. 买卖股票的最佳时机 III、0309. 含冷冻期 等系列问题的 DP 状态机框架。题目描述与约束给定一个整数数组prices其中prices[i]表示某支股票第i天的价格。在每一天你可以决定是否购买和/或出售股票且任何时候最多只能持有一股不过你可以在同一天多次买卖该股票只要保证持有的股票不超过一股即可。要求返回能获得的最大利润。示例 1输入prices [7,1,5,3,6,4] 输出7 解释在第 2 天价格 1买入第 3 天价格 5卖出利润 5 - 1 4。 随后在第 4 天价格 3买入第 5 天价格 6卖出利润 6 - 3 3。 最大总利润为 4 3 7。示例 2输入prices [1,2,3,4,5] 输出4 解释在第 1 天价格 1买入第 5 天价格 5卖出利润 5 - 1 4。示例 3输入prices [7,6,4,3,1] 输出0 解释价格持续下跌交易无法获得正利润不参与交易即可获得最大利润 0。数据约束1 prices.length 3 * 10^40 prices[i] 10^4由于n最大可达 3 万算法必须控制在 O(n log n) 甚至 O(n) 量级本文给出的贪心与动态规划写法均为 O(n) 时间、O(1) 或 O(n) 空间完全满足限制。思路总览为什么只在上涨段交易就是最优本题与 0121. 买卖股票的最佳时机只能交易一次最大的区别是交易次数不限因此不必寻找唯一的最低谷与最高峰而应该捕捉价格曲线上的每一段上涨。有一个关键性质支撑贪心策略的正确性把一段连续上涨[a1, a2, ..., ak]的收益拆成相邻两天的差价之和与谷底买入、峰顶卖出的单次交易收益完全相等(ak - a1) (a2 - a1) (a3 - a2) ... (ak - ak-1)也就是说持有并跨越一整段上涨与每天低买高卖、逐段接力在数学上是等价的。因此我们只需要遍历相邻两天凡遇到prices[i] prices[i-1]就累加这段正差价遇到下跌或持平则跳过。最终累加值即为最大利润。仓库中的中文题解 README.md 将这一策略概括为所有上涨交易日都做买卖所有下跌交易日都不做买卖最终获得的利润是最大的。方法一贪心算法从第二天下标 1开始若当天股价高于前一天就在前一天买入、当天卖出否则不操作。对每个相邻对计算max(0, prices[i] - prices[i-1])并累加即可。Python3class Solution: def maxProfit(self, prices: List[int]) - int: return sum(max(0, b - a) for a, b in pairwise(prices))这里借助 Python 3.10 的pairwise迭代工具把相邻两天两两配对一行完成累加。Javaclass Solution { public int maxProfit(int[] prices) { int ans 0; for (int i 1; i prices.length; i) { ans Math.max(0, prices[i] - prices[i - 1]); } return ans; } }Cclass Solution { public: int maxProfit(vectorint prices) { int ans 0; for (int i 1; i prices.size(); i) ans max(0, prices[i] - prices[i - 1]); return ans; } };Gofunc maxProfit(prices []int) (ans int) { for i, v : range prices[1:] { t : v - prices[i] if t 0 { ans t } } return }TypeScriptfunction maxProfit(prices: number[]): number { let ans 0; for (let i 1; i prices.length; i) { ans Math.max(0, prices[i] - prices[i - 1]); } return ans; }Rustimpl Solution { pub fn max_profit(prices: Veci32) - i32 { let mut res 0; for i in 1..prices.len() { res (0).max(prices[i] - prices[i - 1]); } res } }JavaScript/** * param {number[]} prices * return {number} */ var maxProfit function (prices) { let ans 0; for (let i 1; i prices.length; i) { ans Math.max(0, prices[i] - prices[i - 1]); } return ans; };C#public class Solution { public int MaxProfit(int[] prices) { int ans 0; for (int i 1; i prices.Length; i) { ans Math.Max(0, prices[i] - prices[i - 1]); } return ans; } }复杂度时间复杂度 O(n)其中 n 为prices数组长度空间复杂度 O(1)仅需一个累加变量。源码对应仓库中 Solution.java、Solution.py、Solution.go 等文件即为贪心写法的可提交实现与文档代码逐行一致。方法二动态规划贪心写法虽然简洁但它没有显式的状态概念难以推广到有交易次数限制III、IV、冷冻期309或手续费714的变体。此时需要引入持股/空仓状态机的 DP 模型。状态定义定义f[i][j]表示第i天交易完成后的最大利润其中j 0当前持有股票j 1当前不持有股票空仓。初始状态为f[0][0] -prices[0]第 0 天买入成本为当日价格其余状态初始为 0。状态转移推导若当前持有股票f[i][0]可能来自两种前一天状态前一天就持有今天什么都不做f[i][0] f[i-1][0]前一天空仓今天买入f[i][0] f[i-1][1] - prices[i]。取两者较大值即f[i][0] max(f[i-1][0], f[i-1][1] - prices[i])。若当前不持有股票f[i][1]同样可能来自两种前一天状态前一天就空仓今天什么都不做f[i][1] f[i-1][1]前一天持股今天卖出f[i][1] f[i-1][0] prices[i]。取两者较大值即f[i][1] max(f[i-1][1], f[i-1][0] prices[i])。合并得到完整的状态转移方程f[i][0] max(f[i-1][0], f[i-1][1] - prices[i]) f[i][1] max(f[i-1][1], f[i-1][0] prices[i])最终答案为f[n-1][1]即最后一天交易完成后不持有股票所能获得的最大利润n 为prices长度。Python3class Solution: def maxProfit(self, prices: List[int]) - int: n len(prices) f [[0] * 2 for _ in range(n)] f[0][0] -prices[0] for i in range(1, n): f[i][0] max(f[i - 1][0], f[i - 1][1] - prices[i]) f[i][1] max(f[i - 1][1], f[i - 1][0] prices[i]) return f[n - 1][1]Javaclass Solution { public int maxProfit(int[] prices) { int n prices.length; int[][] f new int[n][2]; f[0][0] -prices[0]; for (int i 1; i n; i) { f[i][0] Math.max(f[i - 1][0], f[i - 1][1] - prices[i]); f[i][1] Math.max(f[i - 1][1], f[i - 1][0] prices[i]); } return f[n - 1][1]; } }Cclass Solution { public: int maxProfit(vectorint prices) { int n prices.size(); int f[n][2]; f[0][0] -prices[0]; f[0][1] 0; for (int i 1; i n; i) { f[i][0] max(f[i - 1][0], f[i - 1][1] - prices[i]); f[i][1] max(f[i - 1][1], f[i - 1][0] prices[i]); } return f[n - 1][1]; } };Gofunc maxProfit(prices []int) int { n : len(prices) f : make([][2]int, n) f[0][0] -prices[0] for i : 1; i n; i { f[i][0] max(f[i-1][0], f[i-1][1]-prices[i]) f[i][1] max(f[i-1][1], f[i-1][0]prices[i]) } return f[n-1][1] }C#public class Solution { public int MaxProfit(int[] prices) { int f1 -prices[0], f2 0; for (int i 1; i prices.Length; i) { f1 Math.Max(f1, f2 - prices[i]); f2 Math.Max(f2, f1 prices[i]); } return f2; } }复杂度时间复杂度 O(n)空间复杂度 O(n)需要保存每一天的两个状态n 为prices数组长度。源码对应仓库中的 Solution2.java、Solution2.go 即为二维 DP 的可提交实现。注意 C# 版本已经直接用两个滚动变量f1、f2书写本质上是方法三的写法。方法三动态规划空间优化观察方法二的状态转移方程可以发现第i天的状态只依赖第i-1天的两个状态与更早的天数无关。因此不必保存完整的n x 2二维数组只需用两个或一组长度为 2 的滚动变量维护前一天的持股/空仓状态即可把空间复杂度从 O(n) 降到 O(1)。Python3class Solution: def maxProfit(self, prices: List[int]) - int: n len(prices) f [-prices[0], 0] for i in range(1, n): g [0] * 2 g[0] max(f[0], f[1] - prices[i]) g[1] max(f[1], f[0] prices[i]) f g return f[1]这里先用临时数组g计算第i天的两个状态再整体替换f避免在同一轮内用更新后的值污染前一天状态。Javaclass Solution { public int maxProfit(int[] prices) { int n prices.length; int[] f new int[] {-prices[0], 0}; for (int i 1; i n; i) { int[] g new int[2]; g[0] Math.max(f[0], f[1] - prices[i]); g[1] Math.max(f[1], f[0] prices[i]); f g; } return f[1]; } }Cclass Solution { public: int maxProfit(vectorint prices) { int n prices.size(); int f[2] {-prices[0], 0}; for (int i 1; i n; i) { int g[2]; g[0] max(f[0], f[1] - prices[i]); g[1] max(f[1], f[0] prices[i]); f[0] g[0], f[1] g[1]; } return f[1]; } };Gofunc maxProfit(prices []int) int { n : len(prices) f : [2]int{-prices[0], 0} for i : 1; i n; i { g : [2]int{} g[0] max(f[0], f[1]-prices[i]) g[1] max(f[1], f[0]prices[i]) f g } return f[1] }复杂度时间复杂度 O(n)空间复杂度 O(1)。源码对应仓库中的 Solution3.py、Solution3.go 即为滚动变量优化的可提交实现。三种解法对比与选型解法核心思想时间复杂度空间复杂度适用场景方法一贪心只累加相邻正差价O(n)O(1)本题专用代码最短、最直观方法二动态规划持股/空仓状态机 二维 DPO(n)O(n)可推广到次数限制、冷冻期、手续费等变体方法三DP 空间优化滚动变量维护前一天状态O(n)O(1)既有 DP 的通用性又有贪心般的空间效率从工程与面试的角度看方法一是最推荐的秒杀写法逻辑简单、不易出错方法二的价值在于建模能力——把状态显式化后只要在状态机里增加一个维度已交易次数或一种限制冷冻期、手续费就能平滑迁移到整个买卖股票系列方法三则是常数优化的标准手法适合在方法二通过后再要求空间优化的场景。延伸买卖股票系列问题掌握了本题的状态机模型后可以顺藤摸瓜练习 doocs/leetcode 仓库中的同系列题目体会交易次数限制、冷冻期、手续费是如何通过扩展状态实现的0121. 买卖股票的最佳时机只能交易一次贪心退化为找最大单次差价0123. 买卖股票的最佳时机 III最多交易两次DP 状态需增加交易次数维度0188. 买卖股票的最佳时机 IV最多交易 k 次是 III 的通用化0309. 买卖股票的最佳时机含冷冻期卖出后需冷冻一天需增加第三种状态0714. 买卖股票的最佳时机含手续费每次交易扣除固定手续费只需在买入/卖出时减去费用。这些题目在仓库中均配有中英双语题解与多语言实现可与本文的贪心、DP、DP 优化三套代码对照学习形成完整的知识闭环。小结贪心视角交易次数不限时逢涨即赚的逐日差价累加是最优解时间复杂度 O(n)、空间 O(1)代码极其精简DP 视角持股/空仓状态机f[i][0/1]给出了更通用的建模方式最终答案取f[n-1][1]优化视角利用当天只依赖前一天的性质滚动两个变量即可把 DP 空间降到 O(1)本题完整的中文题解见 README.md英文版见 README_EN.md各语言可提交代码位于同目录下的Solution*系列文件中。赞分享示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐122. 买卖股票的最佳时机 II无限次交易的贪心与动态规划全解析InterviewGuide 力扣刷题笔记122. 买卖股票的最佳时机 II无限次交易的贪心与动态规划全解析InterviewGuide 力扣刷题笔记 本篇技术笔记以 InterviewGuide教程LeetCode 122 买卖股票的最佳时机 II贪心累加所有上升区间的最优策略leetcode 题解仓库详解LeetCode 122 买卖股票的最佳时机 II贪心累加所有上升区间的最优策略leetcode 题解仓库详解 本文基于 leetcode 题解仓库中 1文档教程知识库GitHub_Trending/leetcode1/leetcode买卖股票的最佳时机III动态规划的多状态定义GitHub_Trending/leetcode1/leetcode买卖股票的最佳时机III动态规划的多状态定义 问题定义与场景分析 给定一个数组 price示例工程上一篇终端视频下载工具yoinksTUI组件如何单元测试node:test renderToString完整拆解下一篇Castor sources深度指南如何配置自己的视频源并按TMDB片名ID直接投屏创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考