企业官网建设流程全解析

这道题我前前后后刷了不下一百遍，不管是带人还是自己复习，每次都会重新过一遍。不是因为它难，恰恰是因为它太经典了——LeetCode热题100里的常青树，面试出镜率极高，而且解法背后的思维模式能直接迁移到一大票动态规划问题上。这篇文章我就把买卖股票的最佳时机从头到尾掰开揉碎讲清楚，包括暴力思路为什么不行、一次遍历的贪心解法怎么想到的、代码实现的细节坑、以及它背后那一整个股票系列的变体套路。不管你是刚刷题的新手，还是准备冲刺面试的老手，这篇都值得你花十分钟看完。

1. 题目拆解与最优解思路

1.1 先搞清楚题目到底在问什么

原题是这样的：给定一个数组 prices，其中 prices[i] 表示某支股票第 i 天的价格，你只能选择某一天买入，并在未来某一天卖出，设计一个算法来计算你所能获取的最大利润。如果不能获取任何利润，返回 0。

翻译成人话就是：在一个数组里找两个数，后面的数减前面的数，差值最大。注意两个关键限制——只能买卖一次，而且必须先买后卖。你不能先卖再买，也不能同一天买了马上卖（利润为 0 等于没操作，返回 0 就行）。

这道题之所以被归为“简单”难度，是因为它有一个非常巧妙的贪心解法。但它又是一道典型的“一看答案就懂，自己想不出来”的题，核心原因在于大多数人一开始都往动态规划或者暴力求解的方向想了，而忽略了过程中只需要维护一个最小值和一个最大利润这两个变量。

1.2 暴力解法为什么不可行

拿到这道题，很多人第一反应是双层循环：外层枚举买入日，内层枚举卖出日，记录最大差值。时间复杂度是 O(n²)，空间复杂度 O(1)。提交上去，LeetCode 给的测试用例能过，但数据量一大就超时。

暴力思路最大的问题在于它做了大量重复计算。比如第 1 天买入，你比较了第 2 天到第 n 天的所有卖出价；第 2 天买入，你又比较了第 3 天到第 n 天。这些区间大量重叠，每一次比较都是独立的，没有用到之前已经算出来的信息。

这道题给我们的第一个教训就是：看到数组题，先想能不能一次遍历解决，再想能不能用空间换时间，最后才考虑暴力。O(n²) 的解法在面试里不是不能提，但提完之后一定要能立刻给出优化方案，否则会给面试官留下“只会暴力”的印象。

1.3 一次遍历的贪心核心思想

最优解法其实特别朴素：从左往右遍历数组，用一个变量记录“到目前为止出现过的最低价格”，同时计算“如果我在今天卖出，能赚多少钱”，维护一个最大利润。

为什么这个思路是对的？因为对于每一个卖出日 i，想要利润最大，买入日一定是第 i 天之前价格最低的那一天。这个“最低价格”不需要单独去查，而是随着遍历不断更新就行。

这就是贪心思想的一个典型应用——每一步都做出当前看起来最优的选择（记录当前最低点），并且这个局部最优能推导出全局最优。因为买卖只能做一次，所以不存在“今天卖了明天还能买”的后效性，贪心在这里是成立的。

2. 从暴力到线性的思维演进

2.1 普通人的思维路径

我记得自己第一次做这道题的时候，想的也是暴力。后来看了题解，觉得“维护最小值”这个操作简直是神来之笔，但就是不知道人家是怎么想到的。

后来刷题多了才慢慢总结出来：对于这种“找两个元素，满足某个先后关系下的最大差值”的题，几乎都可以用“记录前缀最值”的思路来解。你不需要知道未来会发生什么，只需要在遍历过程中持续记录已经扫过的部分的最值信息，然后用当前元素和这个最值做运算就够了。

这就是“在线算法”的思维方式：数据一个一个进来，我不需要等到全部看完才能给出答案，而是每来一个数据就能更新当前的局部答案，最终得到全局答案。

2.2 状态定义和转移的另一种视角

虽然这道题可以用贪心做，但为了后续股票系列题（比如可以多次交易、含冷冻期等），我还是建议从动态规划的角度再理解一遍。

定义 dp[i][0] 表示第 i 天结束后，手上不持有股票的最大利润；dp[i][1] 表示第 i 天结束后，手上持有股票的最大利润。转移方程如下：

• dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
• dp[i][1] = max(dp[i-1][1], -prices[i])

注意第二个式子里的 -prices[i]，因为只能买卖一次，所以如果今天买入，我之前一定是没有任何利润的，成本就是 prices[i]，利润就是负数。

这个 DP 版本的时间复杂度也是 O(n)，空间可以优化成 O(1)，但比贪心多了一个状态维度，理解起来更复杂。所以我通常建议：122 题（可以多次交易）之前，先把这个 DP 版搞懂，因为它是后面所有变体的基础模板。

2.3 两种思路的核心对比

贪心和 DP 在本质上其实是相通的：贪心只需要关注“当前最低买入价”和“当前最大利润”两个标量，DP 则维护两个状态数组。对于这道题，贪心写法更简洁，代码也更不容易写错；DP 写法更通用，能平滑过渡到股票系列的其他题目。

我见过不少人在面试时一上来就背模板，结果面试官换个问法就被问住了。这道题的正确打开方式是：先用自然语言把思路讲清楚（“我记录历史最低价，每天算一下卖出收益”），再写代码，最后再解释一下为什么这样是对的。不要上来就默写代码，那样反而显得像是背题。

3. 代码实现与细节坑位

3.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

这段代码里有两个细节值得注意。第一，min_price 初始化为正无穷大而不是 prices[0]，好处是循环体不用单独处理第一天的逻辑，代码更统一。第二，我用的是 elif 而不是两个独立的 if，因为如果当天的价格刷新了最低点，那么当天肯定不可能同时刷新最大利润（价格都创新低了，卖出必然是亏的），用 elif 可以省一次无效计算。

面试时建议用这个版本，因为它的逻辑边界非常清晰，不容易被追问出漏洞。

3.2 Java 版本与 C++ 版本参考

Java 版本：

class Solution { 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; } }

C++ 版本：

class Solution { public: int maxProfit(vector<int>& prices) { int minPrice = INT_MAX; int maxProfit = 0; for (int price : prices) { if (price < minPrice) { minPrice = price; } else if (price - minPrice > maxProfit) { maxProfit = price - minPrice; } } return maxProfit; } };

三种语言写出来几乎一模一样，因为这道题的核心逻辑就这几行，语言差异只在变量类型的表示方式上。实际面试中，如果你熟练掌握其中一门语言，另外两门能看懂就够了。

3.3 容易被问到的边界条件

• 数组长度为 0 或 1：应该返回 0，因为没法完成一次买卖。上面这段代码天然处理了这种情况，循环直接不执行或只有一次不更新，返回值是初始的 0。
• 数组严格递减：比如 [5,4,3,2,1]，最大利润应该是 0，因为怎么买卖都是亏，不如不操作。上面的代码也天然处理了，因为 max_profit 永远不会被更新。
• 数组严格递增：比如 [1,2,3,4,5]，最大利润是 4，第一天买最后一天卖。代码会在最后一天把利润更新到最大值，逻辑正确。

这些边界条件建议在面试时主动说出来，不需要等面试官问，这是加分项。

4. 股票系列变体一网打尽

4.1 从一次交易到无限次交易

LeetCode 热题 100 里其实不止这一道股票题，同系列的还有 122（可以无限次交易）、123（最多两笔交易）、188（最多 k 笔交易）、309（含冷冻期）、714（含手续费）。这些题在周赛和面试里出现的频率也不低，而且搜索关键词里经常能看到“力扣热题100”“leetcode题解”这类相关检索。

先说 122 题。它可以无限次交易，但同一天不能同时买入和卖出（实际规则），那么贪心策略就变成了：只要今天的价格比昨天高，我就把这段差价赚到手。

def maxProfit(prices): profit = 0 for i in range(1, len(prices)): if prices[i] > prices[i-1]: profit += prices[i] - prices[i-1] return profit

这个策略叫“峰谷法”或者“差分法”，思路是：一段上升趋势的总利润等于所有相邻差价为正的累加。你不需要关心哪天买入哪天卖出，只需要把所有正差价加起来就行。

4.2 状态机 DP：股票题的统一解法

123 和 188 是更复杂的变体，很难用简单的贪心解决，这时候就需要状态机 DP 出场。以 123 题（最多两笔交易）为例，可以定义四个状态：

• buy1：第一次买入后的最大利润
• sell1：第一次卖出后的最大利润
• buy2：第二次买入后的最大利润
• sell2：第二次卖出后的最大利润

转移关系是：buy1 = max(buy1, -prices[i])，sell1 = max(sell1, buy1 + prices[i])，buy2 = max(buy2, sell1 - prices[i])，sell2 = max(sell2, buy2 + prices[i])。

这个套路理解了以后，188 题就是把 buy 和 sell 各开一个长度为 k 的数组，循环更新。所谓的“hard 题”，本质上就是在简单题的状态上多做几层，并没有更玄乎的东西。

4.3 与“爱吃香蕉的狒狒”这类题目的对比思考

最近搜索热词里出现了“leetcode 073爱吃香蕉的狒狒”和“leetcode 1273”这些题号，说明很多人在按题号刷题。其实 875 题（爱吃香蕉的狒狒）是典型的二分答案题，和买卖股票的贪心不是一个套路；1273 题则是树形 DP。它们之间唯一的共通点就是：都是 LeetCode 上被标记为热门的经典题。

我个人的刷题建议是：不要按题号顺序刷，而是按“数据结构/算法标签”分类刷。比如贪心刷一组、DP 刷一组、二分刷一组，这样你才能看到同一算法在不同题目里的变形方式，理解才能深入。买卖股票这组题就是绝佳的 DP 过渡教材：从一次交易到多次交易，从递推公式到状态机，一整套下来你的 DP 基础能扎实不少。

5. 常见问题与面试坑位实录

5.1 面试时千万别踩的输入输出坑

有些面试平台出的题不是纯粹写函数，而是让你处理标准输入输出，比如从控制台读入一个数组，输出最大利润。这种场景下有几个特别容易踩的坑：

• 输入格式可能是 “[7,1,5,3,6,4]” 带方括号和逗号的字符串，需要先去掉括号再按逗号分割转成 int 数组。
• 数组中每个数字占一层输入，记得用 while (cin >> x) 或者 hasNextInt() 循环读。
• 读完后可能有换行符或空格残留，Java 里要用 nextInt() 而不是 nextLine() 拼着用。
• 极端情况下 prices 里可能出现负数（虽然题目约定非负），建议代码里至少别因为负数而报错。

5.2 现场推导和复杂度分析的应对话术

面试官大概率会追问“时间复杂度多少”“能不能优化”。你要能脱口而出：一次遍历 O(n)，只有两个临时变量所以空间 O(1)。不能只说结论，最好补一句“因为只扫描了一遍数组，每一步维护历史最低价和当前最大收益，所以是线性的”。

还有一个高频追问是：“如果数组很长，内存装不下怎么办？”这种属于发散题，你可以回答外排序后分块处理，或者流式处理——因为这个算法本来就是在线算法，数据不用全部载入内存，来一个处理一个，这反而是这道题的一个隐藏优点。

5.3 我踩过的一些细节坑

• 用 float('inf') 初始化最小值，但如果你在 Go 语言里这么写，得用 math.MaxInt64 或者直接取 prices[0]，否则类型转换很麻烦。
• 有一些题解喜欢用动态规划 + 滚动数组，代码写成 dp0 和 dp1 两个变量，其实思路与贪心殊途同归，但如果你说不清 dp0 和 dp1 的含义，面试官一追问题就露馅。
• 返回值类型：Java 的 int 足够存数组长度为 10^5、价格最大 10^4 时的最大利润，不会溢出，所以不用考虑 long。但如果你做过一些变形题，比如价格范围变成 10^9，那就要注意用 long 了。
• C++ 里要小心 vector 为空的时候取 prices[0] 会直接运行时错误，所以边界判断一定要写在前面。

6. 从这一题延伸出的刷题心法

6.1 为什么每道经典题都值得反复刷

热题 100 之所以经典，是因为这些题背后对应的算法思维在真实面试里反复出现。买卖股票这道题考察的不只是“你会不会写这个函数”，而是考察你能否从暴力循环中提炼出“前缀最值”这一思维模式，并用它去解决看似不同、本质相同的其他题目。

我认识不少人刷题喜欢贪多，一天十几道，刷完就忘。我的方法是：每道题至少隔一周刷一遍，第三遍时直接白板手写并讲思路，能做到这步才算是真正掌握了。经典题刷三遍，效果远超新题刷一遍。

6.2 如何把这道题的思路迁移到其他题目

“前缀最值”这个技巧能用在哪？比如 42 号题“接雨水”，本质上是在每个位置找左右两侧的最大值，然后计算能存的水量。再比如 238 号题“除自身以外数组的乘积”，也是用前缀积乘后缀积的思路。

股票题的核心三步走——定义状态、找转移、优化空间——同样适用于 198 打家劫舍、300 最长递增子序列、322 零钱兑换这些入门 DP 题。你会发现，一旦你理解了“每一步只需要关注当前最优解”这个思想，很多题目的解法都是同一个套路换皮。

6.3 周赛和真实面试的差异感

最近力扣周赛已经到了 430 场左右，周赛里的题往往需要组合多个技巧，一道题可能同时用到贪心、二分、前缀和、并查集。相比之下，热题 100 里的题更像是“基础功”，就像武术里的扎马步。

但不要小看基本功。我面试别人的时候，宁愿候选人把这一道简单题讲得透彻、答得出所有追问，也不愿意看到一个背了三道 hard 题答案却讲不清思路的人。基础题的深度，往往才是区分有没有真正理解算法的试金石。

6.4 绕不开的“题感”问题

刷题刷到最后，其实就是练题感。看到“买卖股票”知道是贪心或者状态机 DP，看到“爱吃香蕉的狒狒”知道是二分答案，看到“二叉树最大路径和”知道是树形 DP——这种条件反射，只能用大量练习堆出来。

如果你现在还在新手期，我的建议是先把热题 100 里动态规划那十几道题全部弄清楚，然后按股票系列、背包系列、子序列系列、路径系列分组巩固。这个过程不用急，但是每一步都要走扎实。

我自己在刷这道题的过程中，最大的一个体会就是：真正难的从来不是那道题本身，而是你有没有一套自己熟悉的思维框架去分析它。买卖股票的最佳时机这道题，是极少数能把“贪心”“DP”“在线算法”“边界处理”这几个知识点串在一道题里的题目，吃透它的价值远远超过了这 5 分钟本身。希望这篇文章能帮你把它真正变成自己的东西。