LeetCode-Go 题解 | 121. Best Time to Buy and Sell Stock一次交易的最大利润动态规划与单调栈双解法【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本题是股票买卖系列的开篇题也是最多一次交易模型的经典入门题给定一支股票连续 N 天的价格数组要求算出只进行一次买入卖出所能获取的最大利润且必须先买后卖。本文以 leetcode/0121.Best-Time-to-Buy-and-Sell-Stock/README.md 为核心文档结合 121. Best Time to Buy and Sell Stock.go 中的两套完整 Go 实现模拟 DP 与单调栈及其 测试用例讲透问题本质、两种算法的推导过程与复杂度对比。读完本文你将掌握这一题型的标准解法模板为后续 122/123/188 等多次交易带冷却变体题打下基础。题目给定一个数组它的第i个元素是一支给定股票第i天的价格。如果你最多只允许完成一笔交易即买入一股并卖出一股设计一个算法来计算你所能获取的最大利润。注意你不能在买入股票前卖出股票。示例 1Input: [7,1,5,3,6,4] Output: 5 Explanation: 第 2 天价格 1买入第 5 天价格 6卖出利润 6-1 5。 注意不是 7-1 6因为卖出价格必须大于买入价格。示例 2Input: [7,6,4,3,1] Output: 0 Explanation: 这种情况下不进行任何交易即最大利润 0。题目大意给定一个数组它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易即买入和卖出一支股票设计一个算法来计算你所能获取的最大利润。注意你不能在买入股票前卖出股票。核心约束可以归纳为三点最多一次交易买入、卖出各自最多一次也可以完全不交易此时利润为 0必须先买后卖卖出日必须在买入日之后利润非负由于可以放弃交易答案下界恒为 0。解题思路题目要求找出股票中能赚的钱最多的差价即求数组中满足i j的最大差值prices[j] - prices[i]。这一题有多种解法可以用 DP也可以用单调栈。本仓库在 121. Best Time to Buy and Sell Stock.go 中同时给出了这两种实现下面逐一展开。解法一模拟 DP一次遍历维护历史最低价这是最直观、也是最优的解法。思路是在遍历价格的同时始终记录到当前天为止出现过的历史最低买入价min并用当天价格 - min尝试更新最大利润。// 解法一 模拟 DP func maxProfit(prices []int) int { if len(prices) 1 { return 0 } min, maxProfit : prices[0], 0 for i : 1; i len(prices); i { if prices[i]-min maxProfit { maxProfit prices[i] - min } if prices[i] min { min prices[i] } } return maxProfit }逐行拆解边界处理len(prices) 1时直接返回 0。注意源码用的是 1而非 0语义上等价于处理空数组初始化min取第一天的价格prices[0]maxProfit初始化为 0允许不交易循环体两步操作先用prices[i] - min计算若在今天卖出的利润并更新maxProfit再判断prices[i]是否刷新了历史最低价若是则更新min。两步的顺序保证先买后卖的约束min永远来自i之前的某一天不会出现未来价格被当作买入价的情况。这是一个典型的滚动变量式 DP只需要两个状态历史最低价、当前最大利润空间复杂度被压到 O(1)时间复杂度为单次遍历 O(n)。它同时正确处理了题目给出的两个示例[7,1,5,3,6,4]在第 2 天以 1 买入、第 5 天以 6 卖出得 5[7,6,4,3,1]价格一路下跌prices[i]-min始终为负maxProfit保持 0即不交易。解法二单调栈原文档指出本题也可用单调栈求解仓库给出了对应的完整实现// 解法二 单调栈 func maxProfit1(prices []int) int { if len(prices) 0 { return 0 } stack, res : []int{prices[0]}, 0 for i : 1; i len(prices); i { if prices[i] stack[len(stack)-1] { stack append(stack, prices[i]) } else { index : len(stack) - 1 for ; index 0; index-- { if stack[index] prices[i] { break } } stack stack[:index1] stack append(stack, prices[i]) } res max(res, stack[len(stack)-1]-stack[0]) } return res } func max(a int, b int) int { if a b { return a } return b }这里的思路可以这样理解用一个递增栈维护到当前天为止、以历史最低点为起点的递增价格序列栈底永远是历史最低价stack[0]栈顶是当前波峰stack[len(stack)-1]当新价格高于栈顶波峰仍在上涨时直接入栈栈底与栈顶的差值就是当前这一段的最大利润当新价格低于栈顶时说明上涨行情结束从栈顶向下弹出所有不低于新价格的元素找到第一个比新价格小的位置index截断后把新价格压入栈——相当于重新锚定一段更低的行情起点每轮迭代后用res max(res, stack[len(stack)-1]-stack[0])更新全局答案其中stack[0]是栈内最低价、stack[len(stack)-1]是栈内最高价。两种解法的执行轨迹一致单调栈本质上是把历史最低价以单调栈的形式显式维护栈底即全局历史最低价因此最终结果与模拟 DP 完全相同。代价是额外 O(n) 的空间最坏情况下栈内元素数量与天数同阶这也是它与解法一的主要差异。复杂度对比解法时间复杂度空间复杂度特点模拟 DPmaxProfitO(n)O(1)单次遍历常数空间推荐单调栈maxProfit1O(n)O(n)栈显式维护低价序列适合与栈专题题组对比学习实际工程与竞赛中解法一的空间开销更优解法二的意义更多在于训练单调栈思维——同一思路经过改造后可以迁移到滑动窗口极值直方图最大矩形等进阶题型。测试与验证本仓库对每道题配有 100% 覆盖率的表驱动测试本题的测试位于 121. Best Time to Buy and Sell Stock_test.go。测试数据覆盖了四类典型场景输入预期输出场景说明[]0空数组边界[7,1,5,3,6,4]5题面示例先跌后涨一次交易获利[7,6,4,3,1]0全程下跌放弃交易[1,3,2,8,4,9]8非单调波动最优为 1 买入、9 卖出测试用例通过para121/ans121结构体组织输入与期望输出遍历用例时同时调用maxProfit与maxProfit1两个实现并打印输入输出确保两种解法在全部场景下结果一致。若要在本地运行该用例可执行仓库模块名见 go.modgo test ./leetcode/0121.Best-Time-to-Buy-and-Sell-Stock/ -v延伸阅读本题是单次交易模型的基础其加强版可多次交易见 122. Best Time to Buy and Sell Stock II核心思路是捕捉每一段上升区间两两相减累加单调栈是 LeetCode 中的高频专题仓库 topic/Stack.png 汇总了栈相关题组可供体系化刷题参考本仓库在 go.mod 中通过 replace 指令将structures、template等子包替换为本地目录全部题解位于leetcode/目录下每题都遵循题解实现 表驱动测试 README 讲解三件套的组织方式。总结LeetCode 121 考察的核心是在 O(n) 时间内求后值减前值的最大差。模拟 DP 通过滚动维护历史最低价一步到位是面试中的最优解单调栈则提供了同一问题的另一种建模视角有助于打通栈维护极值的方法论。结合本仓库的源码与测试用例建议读者先手写解法一再用解法二对照验证最后尝试将两种思路迁移到 122 题的多笔交易场景完成从单题到题组的认知闭环。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考