尧图网络 高端网站定制 · 原创设计
免费咨询热线
400-888-6620
免费获取方案
LeetCode 121股票买卖问题:最优解法与动态规划应用
1. 题目解析与核心思路LeetCode 121题Best Time to Buy and Sell Stock是算法面试中的经典问题主要考察对数组遍历和动态规划思想的理解。题目要求给定一个数组prices其中prices[i]表示某支股票第i天的价格你需要选择某一天买入并在未来某一天卖出计算可能获得的最大利润。1.1 问题重述假设我们有一个数组[7,1,5,3,6,4]我们需要找到买入和卖出的最佳时机。在这个例子中最佳策略是在第2天价格为1买入第5天价格为6卖出获得最大利润5。注意你不能在第2天买入后在第1天卖出因为卖出必须在买入之后。1.2 暴力解法分析最直观的解法是使用双重循环max_profit 0 for i in range(len(prices)): for j in range(i1, len(prices)): profit prices[j] - prices[i] if profit max_profit: max_profit profit return max_profit这种方法的时间复杂度是O(n²)在LeetCode上会超时显然不是最优解。2. 最优解法详解2.1 单次遍历法更高效的解法是只遍历一次数组在遍历过程中记录当前遇到的最小价格并计算当前价格与最小价格的差值作为潜在利润def maxProfit(prices): min_price float(inf) max_profit 0 for price in prices: if price min_price: min_price price elif price - min_price max_profit: max_profit price - min_price return max_profit这个算法的时间复杂度是O(n)空间复杂度是O(1)非常高效。2.2 算法正确性证明为什么这种方法能保证找到最大利润因为我们始终记录着到当前为止的最低买入价每次遇到更高的价格时都计算可能的利润只保留最大的利润值这样就能确保不会错过任何可能的更高利润组合。3. 边界条件与特殊测试用例3.1 常见边界情况价格持续下跌[7,6,4,3,1] → 应返回0不交易空数组[] → 应返回0单元素数组[7] → 应返回0价格相同[2,2,2,2] → 应返回03.2 测试用例设计技巧在面试中除了给出标准解法外主动讨论边界条件会加分。建议准备以下测试用例常规情况有利润无利润情况极小/极大值空输入单日输入4. 算法优化与变种4.1 空间优化版本虽然原解法已经是O(1)空间但可以更简洁def maxProfit(prices): min_price, max_profit float(inf), 0 for price in prices: min_price min(min_price, price) max_profit max(max_profit, price - min_price) return max_profit4.2 类似问题扩展允许多次交易LeetCode 122最多两次交易LeetCode 123最多k次交易LeetCode 188含冷冻期LeetCode 3095. 实际应用场景这类算法问题虽然简单但在实际金融交易系统中非常重要高频交易系统需要实时计算最佳买卖点量化投资策略中的趋势判断投资组合优化6. 常见错误与调试技巧6.1 新手常见错误忘记初始化min_price为极大值将max_profit初始化为负值应为0混淆买入和卖出的时间顺序6.2 调试建议打印每次循环的min_price和max_profit用简单测试用例手动验证特别注意数组为空或单元素的情况7. 性能分析与比较7.1 时间复杂度对比方法时间复杂度空间复杂度适用场景暴力法O(n²)O(1)不推荐单次遍历O(n)O(1)推荐动态规划O(n)O(n)复杂变种7.2 实际运行测试在LeetCode测试平台上单次遍历法的运行时间通常在40-60ms之间Python3击败90%以上的提交。8. 代码实现细节8.1 Python实现优化使用内置函数可以略微提升性能def maxProfit(prices): min_price, max_profit float(inf), 0 for price in prices: min_price min(min_price, price) max_profit max(max_profit, price - min_price) return max_profit8.2 Java实现示例public int maxProfit(int[] prices) { int minPrice Integer.MAX_VALUE; int maxProfit 0; for (int price : prices) { if (price minPrice) { minPrice price; } else if (price - minPrice maxProfit) { maxProfit price - minPrice; } } return maxProfit; }9. 面试技巧与回答策略9.1 面试官可能追问的问题如何证明你的算法是正确的如果允许多次交易怎么做如果交易有手续费怎么处理如何扩展到多支股票9.2 回答策略建议先给出暴力解法再优化主动讨论时间/空间复杂度提出测试用例讨论可能的扩展10. 学习资源推荐《算法导论》动态规划章节LeetCode股票买卖问题系列121-188题《编程珠玑》中的算法优化思想极客时间的算法面试精讲课程在实际刷题过程中我发现很多同学容易忽视边界条件的检查。比如当输入数组为空时直接开始计算导致运行时错误。建议养成先检查输入有效性的习惯这在面试中也是加分项。
RELATED

相关推荐

Chat-嬛嬛实战:用提示词工程与多轮对话管理稳住人设

Chat-嬛嬛实战:用提示词工程与多轮对话管理稳住人设

第一天打卡,我们做的东西说出来有点不正经——一个满口“本宫”、会跟你抬杠、也会絮絮叨叨讲家常的聊天机器人,内部代号Chat-嬛嬛。这是 DataWale 大模型学习计划 Day1 的练手项目,目标很朴素:不训练、不微调、不碰显卡&#xff…

📅 2026/11/2 2:37:22
Docker容器化CPLEX:Java求解服务环境一致性与部署实践

Docker容器化CPLEX:Java求解服务环境一致性与部署实践

简介:这份资源面向需要在容器环境中运行 IBM ILOG CPLEX 的 Java 开发者与运筹优化学习者,解决 CPLEX 本地部署依赖复杂、跨平台环境配置繁琐的问题。包内共 7 个文件,以 Dockerfile 为主,配合 Java 示例源码、CPLEX 模型文件、pr…

📅 2026/11/2 2:37:22
Vue DevTools 6.6.4离线安装与调试面板排障指南

Vue DevTools 6.6.4离线安装与调试面板排障指南

简介:这是一份面向Vue.js 3开发者的Chrome调试扩展包,版本固定为6.6.4,主要用于在浏览器中观察Vue应用的组件层级、响应式状态、事件监听与路由切换,并辅助定位渲染异常和性能瓶颈。压缩包共128个文件,约2.12MB&#x…

📅 2026/11/2 2:32:21
MORE NEWS

更多资讯

📰

Gemini 4 Pro实测对决Claude Opus 5.5:推理与Agent工具调用全面领先

Gemini 4 Pro 的全新曝光消息今天下午刷屏,我这边其实提前拿到了 preview API 配额,趁着热度把 Claude Opus 5.5 拉到同一个擂台上实测了一轮。两天下来,结果比预期更集中:在自建的 25 个高难度任务中,Gemini 4 Pro 在…

📰

Agent工具调用重复循环:为什么砸钱训练治不好?

这种问题我见过太多了,所以看到 MiMo-V2.6 这个标题时,我第一反应不是嘲笑,而是想叹气。一个模型开始重复调用工具,团队为了修这个毛病,额外砸进去 227 万美元训练费,最后问题还在。翻译成大白话就是&#…

📰

SSD全盘加密落地:BitLocker与LUKS2参数、性能与恢复

一台笔记本用了三年准备转手,或者送维修点换个风扇,很多人的第一反应是"把文件删了、回收站清空"。我见过太多这种操作,包括一些自认为懂点技术的朋友。实际上你删掉的只是文件系统的索引,NAND 闪存里的电荷一个都没少&…

📰

MS-900备考四类致命错误:从刷题到许可模型与模拟复盘

MS-900这门考试,我前后考了两次才过。第一次考完还剩十几分钟,心里还挺美,点交卷那一刻觉得自己稳了,结果分数弹出来差了一大截。复盘的时候才发现,挂掉的不是知识量,而是备考方式——我把一门讲“云服务全…

📰

OpenClaw与企业微信对接实战指南

1. OpenClaw与企业微信对接项目概述OpenClaw作为一款新兴的自动化工具平台,其与企业微信的深度整合正在成为企业数字化办公的热门解决方案。这个组合最吸引人的地方在于,它能让传统企业通讯工具获得智能自动化能力。想象一下,当你的企业微信突…

📰

DeepSeek-V3 MLA注意力机制:KV Cache压缩与长上下文推理优化

多头潜在注意力机制(Multi-head Latent Attention,MLA)是 DeepSeek-V3 在模型架构层面最值得拿出来单独讲的一项改动。我第一次读到相关技术报告时,最直观的感受不是"又出了一个新注意力变体",而是它把推理阶…

TODAY

今日更新

THIS WEEK

本周精选

THIS MONTH

本月热门

读完文章,想聊聊您的网站?

告诉我们您的行业与需求,资深顾问一对一梳理方案与报价,全程免费。

📞 💬