我记得很清楚，第一次看到“买卖股票的最佳时机”这道题时，我还在按部就班地刷LeetCode热题100。当时群里有人说这题“秒了”，我心想估计又是那种背个模板就能过的题。结果自己动手一写，暴力解法提交直接超时，吓得我赶紧去看题解，发现最优解居然只有十几行。代码是背下来了，但心里一直不踏实——为什么记录一个最低价就能算出最大利润？为什么内层循环可以被一个变量替代？后来我把从暴力到贪心的完整推导过程走了一遍，才算真正把这道题吃透。这篇就把这条推导链路完整拆开，用Java一步步写给你看，适合刚接触算法题的读者，也适合准备面试、想把“会背”变成“会讲”的人。
1. 题面解读：一次买入一次卖出，利润到底从哪来
1.1 输入输出与两条隐含规则
题目给你的东西很简单：一个数组prices，prices[i]表示第i天的股票价格。你要做的事情是选某一天买入，再选之后的某一天卖出，让两次操作的差价最大。如果无论如何都赚不到钱，就返回 0。
这里藏着两条新手很容易忽略的隐含规则：
第一，只能完成一次交易。买一次、卖一次，不能今天买了明天卖，后天再买再卖，那是 LeetCode 122 题“允许多次交易”的玩法。121 题把交易次数锁死在一次，这让问题简单了很多，但也让很多习惯做“低买高卖波段”的人一时转不过弯来。
第二，卖出日必须在买入日之后。哪怕你能预知明天要暴跌，也不能先卖后买，这在数组下标上体现为严格的i < j关系。很多人在推导状态转移时把i和j搞反，或者写成了i <= j，就会出现“当天买入当天卖出利润为 0”这种看似无害却语义错误的情况。
一个容易被忽略的认知是：题目并不要求你实际执行任何交易。它只是让你计算“如果交易，最多能赚多少”。这意味着如果所有方案都亏钱，你完全可以不买不卖，利润就是 0。这个“允许不交易”的设定，直接决定了后面maxProfit的初始值不能是负数。
1.2 边界情况：空数组、只有一天、一路下跌
边界条件经常是提交失败的第一现场。如果prices长度为 0 或者只有 1 个元素，根本不存在“买入之后再卖出”的完整交易，直接返回 0。很多人写代码上来就访问prices[1]，遇到单元素数组直接数组越界。
还有一种更隐蔽的情况：数组整体递减，比如[7, 6, 4, 3, 1]。无论你在哪一天买入，之后都找不到更贵的价格卖出，所有利润都是负数。按规定要返回 0，而不是返回某个负的最大值。我在本地测试时见过有人把maxProfit初始化为Integer.MIN_VALUE，然后一路取最大，最后返回一个负数——这在数学上没错，但不符合题目要求。
所以拿到题的第一件事，我建议先列边界清单：空数组、单元素、全递增、全递减、先跌后涨、有重复价格。列完之后再动笔写代码，能省掉大量调试时间。
1.3 先想暴力，不是浪费时间
我知道很多人刷题有一个倾向：看到题解区都是 O(n) 的贪心写法，就直接跳过暴力版本，觉得“反正最优解都知道了，还写什么慢的”。但我自己的体会是，跳过暴力意味着你根本没建立起“这个问题最优解长什么样”的直觉。
暴力解虽然慢，但它把所有的买入卖出组合都枚举了一遍。你盯着它看一会儿，会发现答案一定来自“某个低点买入，之后某个高点卖出”这个结构。后面所有优化，本质上都是在压缩这个结构里的冗余计算。理解这一点，比背下十行代码重要得多。
2. 暴力解法：最朴素的双层循环，以及它的复杂度瓶颈
2.1 双层循环的 Java 实现
暴力解法非常直白：枚举所有可能的买入日i，再枚举所有在i之后的卖出日j，计算prices[j] - prices[i]，不断更新最大值。
public int maxProfit(int[] prices) { int n = prices.length; int maxProfit = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int profit = prices[j] - prices[i]; if (profit > maxProfit) { maxProfit = profit; } } } return maxProfit; }这段代码的循环次数是组合数 C(n, 2) = n(n-1)/2。n 是数组长度，比如 n = 6 时内层总共执行 15 次；n = 100 时是 4950 次。它把每一种“先买后卖”的可能性都算了一遍，没有任何遗漏。作为正确答案而言，它在逻辑上是完备的——唯一的缺点是慢，而且慢得离谱。
我在本地第一次跑这个版本时，用随机生成的长度为 10 万的数组测试，耗时大概 6 秒多。作为一个刷题解法，这基本等于不可用。
2.2 当 n 达到 10^5，暴力为什么会超时
LeetCode 对这道题的输入规模，prices长度最大能到 10^5 的量级。代入公式算一下：n = 100000 时，n(n-1)/2 ≈ 5 × 10^9 次操作。
5 × 10^9 是什么概念？现代 CPU 每秒能执行的简单整数运算量级大约在 10^8 到 10^9 之间，这还要看具体语言和编译器优化情况。Java 跑这种纯计算循环，5 × 10^9 次减法和比较，乐观估计也要好几秒。而 LeetCode 这类在线判题系统通常把时限压到 1 秒左右。所以暴力版本提交上去，结果基本都是 Time Limit Exceeded，也就是俗称的超时。
这里我多说一句：很多人把超时简单归因为“数据太大”，但更准确的理解是“算法的时间增长太快”。暴力解法的耗时随 n 呈平方级增长，n 每翻一倍，耗时变成原来的 4 倍。这种增长速度在工程上是非常可怕的——哪怕 n 只有一万，循环次数也有约 5000 万次，如果再叠加上其他操作，已经能感受到明显的卡顿。
2.3 暴力解法的价值：它揭示了答案的结构
暴力解虽然过不了测试，但它在思路上极其重要。它告诉我们：最大利润一定来自“某个买入日 i + 某个卖出日 j”，并且 i 在 j 之前。这个结构在任何优化版本里都不会变。
换句话说，优化不是改变答案的形态，而是减少找到这个答案所需的计算量。这个认知在面试里尤其值钱——面试官不太在乎你能不能背出贪心代码，更在乎你能不能从暴力出发，说清楚“冗余到底出在哪一步”。如果你一上来就抛出minPrice和maxProfit两个变量，面试官只会觉得你背过题；但如果你能指着双层循环说“内层循环其实在重复计算历史最小值”，对方才会觉得你真的理解这道题。
暴力还给了我们一个可以对照验证的基准。后面写出贪心版本后，我会先用暴力的结果去验证正确性，确认两者输出一致，再交给大数据测试。这个习惯让我少犯很多低级错误。
3. 从暴力到贪心的关键一步：压缩买入日的枚举
3.1 数学化观察：每个卖出日只需要知道历史最低价
现在回到暴力解法，重新看它到底在算什么。对每一个固定的卖出日j，它把第 0 天到第 j-1 天都当成可能的买入日，逐个计算prices[j] - prices[i]，然后取最大值。
但仔细看这些差值，你会发现一个事实：对于固定的j来说，prices[j]是不变的，要让prices[j] - prices[i]最大，等价于让被减数prices[i]最小。所以，对固定卖出日j，我们真正要找的并不是“哪一天买入利润最大”，而是“第 0 天到第 j-1 天里哪天价格最低”。
这个观察非常关键。它意味着：内层循环的枚举目标，从“所有买入日”坍缩成了“一个最低价格”。只要知道历史最低价，买入日就自动确定了，不需要再为每个j重新枚举一遍i。
用公式来描述就是：令f(j)表示在第 j 天卖出能获得的最大利润，那么
f(j) = prices[j] - min(prices[0], prices[1], ..., prices[j-1])最终答案等于max(0, max(f(1), f(2), ..., f(n-1)))。如果直接用公式计算每个f(j)都要重新扫一遍前缀，那还是 O(n²)，但如果从左到右扫一次，边扫边维护“到目前为止见过的最低价格”，每个f(j)就能 O(1) 算出。这就是整个优化最核心的一步。
3.2 生活化类比：记录你见过的油价最低点
我特别喜欢用一个类比来理解这件事。假设你从家开车去机场，一路上会经过很多加油站，每个加油站油价不一样。你想知道的是：如果只能在已经路过的加油站加过油，那么开到哪个加油站时油箱最“值”——也就是用当前油价减历史最低油价，什么时候差价最大。
答案很简单，你只需要记住一路上见过的最低油价。每到一个新加油站，用“当前油价减历史最低油价”算一下差额，如果比之前记的最大差额大，就更新它；如果当前油价本身创了新低，就更新最低油价记录。整个过程只需要记一个数字，不需要把每家加油站的价钱都记下来，更不需要每到一家就回头把前面所有加油站重新比一遍。
暴力解法就是那个“记下所有油价，之后每家都反复回头比较”的笨办法；贪心版本则是“边走边记住最低油价”的聪明办法。两者得到的答案完全一样，但后者省掉了一整个维度的重复劳动。
3.3 这一步为什么让复杂度从 O(n²) 降到 O(n)
把“枚举所有买入日”变成“一边遍历一边维护历史最低价”，本质上是把二维的遍历压缩成一维的遍历，代价只需要额外记住一个变量。
具体来说，我们只需要从左到右扫一次数组。每一步做两件事：第一，拿当前价格减去历史最低价，尝试更新最大利润；第二，拿当前价格和历史最低价比较，看是否需要更新历史最低价。这两件事都是常数时间操作，所以整体复杂度是 O(n)，额外空间是 O(1)。
这个思想在算法领域有更广的应用：把重复计算前缀信息的暴力循环，改造成边遍历边维护聚合信息的单次循环。股票系列后面的 122 题、123 题、188 题，本质上都在这个基础上加入更多状态维度，但这第一层“维护历史最低价”的思维，是整个系列的敲门砖。
顺带回答一个常见问题：为什么这个解法叫贪心？我的理解是，每一步它都基于“当前信息下最优的历史买入点”做决策，并相信这个局部选择能推导出全局最优。严格来说它也可以被解释成动态规划的退化形态，但叫法不重要，重要的是你理解了“维护历史最优信息”这个动作。
4. 贪心实现：Java 代码、变量设计、完整走表
4.1 两个变量，一次遍历
贪心版本的 Java 实现非常干净，核心就是两个变量：minPrice记录遍历到目前为止见过的最低价格，maxProfit记录到目前为止能获得的最大利润。
public int maxProfit(int[] prices) { // 允许不交易，所以卖不出去时利润就是 0 int minPrice = Integer.MAX_VALUE; int maxProfit = 0; for (int price : prices) { if (price < minPrice) { // 当前价格刷新历史最低价，理论上可以在此处买入 minPrice = price; } else { // 否则尝试在当前价格卖出 int profit = price - minPrice; if (profit > maxProfit) { maxProfit = profit; } } } return maxProfit; }minPrice初始化为Integer.MAX_VALUE是很多人的第一反应，目的是让第一个元素一定能成为新的历史最低价。maxProfit初始化为 0，是因为题目允许不交易，如果所有交易都亏钱，返回 0 而不是负数。
这个版本的语义非常清晰：遇到更低的买入价就更新买入点，否则就看看当前价格卖出能赚多少。它天然避免了“当天买入当天卖出”的歧义，因为只有在price >= minPrice时才会去计算利润。
4.2 完整走表演示
拿题目里最常见的示例prices = [7, 1, 5, 3, 6, 4]走一遍，看看两个变量是怎么变化的。
| 天数 | prices[i] | 操作 | minPrice | maxProfit |
|---|---|---|---|---|
| 第0天 | 7 | 7 < MAX_VALUE，更新最低价 | 7 | 0 |
| 第1天 | 1 | 1 < 7，更新最低价 | 1 | 0 |
| 第2天 | 5 | 5 ≥ 1，利润 = 5 - 1 = 4 | 1 | 4 |
| 第3天 | 3 | 3 ≥ 1，利润 = 3 - 1 = 2，未超过4 | 1 | 4 |
| 第4天 | 6 | 6 ≥ 1，利润 = 6 - 1 = 5 | 1 | 5 |
| 第5天 | 4 | 4 ≥ 1，利润 = 4 - 1 = 3，未超过5 | 1 | 5 |
最终返回 5。对应操作是第 1 天买入（价格 1），第 4 天卖出（价格 6），利润 6 - 1 = 5。表格里有一个细节值得注意：在第 2 天时利润已经到 4，但第 4 天才到 5，说明最大利润不一定出现在最后一个元素，所以不能用“遍历结束后拿最后价格减最低价”这种取巧写法，必须每步都尝试更新maxProfit。
4.3 两种常见写法，结果等价但语义略有不同
写这题时，网上会看到两类代码。一类是我上面写的if-else分支版本；另一类是不分支，直接用工具方法：
public int maxProfit(int[] prices) { int minPrice = Integer.MAX_VALUE; int maxProfit = 0; for (int price : prices) { minPrice = Math.min(minPrice, price); maxProfit = Math.max(maxProfit, price - minPrice); } return maxProfit; }在 121 题里，这两种写法结果完全一样。原因是：如果当前价格比历史最低价还低，price - minPrice会变成 0，而maxProfit的初始值是 0，0 不可能大于已有的 0，所以“当天买当天卖”的 0 利润不会污染答案。
但我的建议是优先写if-else分支版本，因为它更贴近“先有买入，才能卖出”的实际交易语义。一旦后面的题目加了冷冻期、手续费、交易次数限制，这个语义细节就会变得非常重要。比如 309 题规定卖出后第二天才能再买，你再用Math.min和Math.max的组合，状态转移很容易绕晕；而用清晰的买入更新逻辑去推，会顺很多。
另外，有些人会把price - minPrice的计算放在if (price < minPrice)之前，也就是无论是否更新最低价都先算一次利润，这在 121 题里不会出错（因为算出来的利润如果是负的，会被Math.max过滤掉），但它会让初学的人对“买入点”这个概念产生混淆。我调试这个版本时，某次在本地打印每一步的minPrice和maxProfit，分明看到某一步里minPrice已经被更新成更低值，但利润还是沿用旧低点算的——虽然结果正确，可读性和理解成本却更高了。
5. 易错点、测试用例设计，以及它和股票系列题目的关系
5.1 容易踩的坑：越界、负利润、无脑背代码
先说说我自己踩过和最常看到别人踩的坑。
第一个坑是数组越界。有人会在循环外先读prices[1]，或者用for (int j = i; j < n; j++)这种写法，导致出现“当天买当天卖”的情况。虽然 121 题里这种情况结果不变（利润 0），但在代码审查时属于逻辑漏洞，面试官很爱揪这种细节。
第二个坑是负利润污染。如果maxProfit初始化为Integer.MIN_VALUE，或者最后直接返回profit而不是Math.max(maxProfit, profit)，遇到一路下跌的数组就会返回负数。记住题目标题里写的“如果没有可实现的利润，返回 0”，这代表允许不交易，是一个合法的“躺平”选择。
第三个坑是背代码而不理解推导。有一次模拟面试，我尝试直接写贪心版本，对方问了一句“为什么一个minPrice就能替代内层循环”。我当时卡住了，因为只记得“好像应该这么写”，却说不出“对每个卖出日，最大利润取决于历史最低买入价”这个本质。从那以后我刷题都要求自己先写暴力再推优化，能讲清楚推导过程才算过。
还有一个实战技巧：在本地调试时，用System.out.println把每步的price、minPrice、profit打出来，尤其是数据量小于 10 的时候。很多时候你以为代码写对了，一打印就发现，minPrice更新的时机和你想的完全不一样。
5.2 自带测试用例怎么设计
刷题不能只靠题目的示例，我习惯在本地再补一组边界用例，确保万无一失：
| 输入 | 期望输出 | 用例意图 |
|---|---|---|
| [7, 1, 5, 3, 6, 4] | 5 | 标准场景 |
| [1, 2] | 1 | 最小可交易场景 |
| [2, 1] | 0 | 先高后低，无法获利 |
| [7, 6, 4, 3, 1] | 0 | 持续下跌 |
| [3, 3, 3] | 0 | 价格持平 |
| [2, 4, 1, 5] | 4 | 多次起伏，答案来自 1 买 5 卖 |
| [1] | 0 | 只有一天，无法交易 |
| [] | 0 | 空数组，防御性判断（LeetCode 可能不传这种，但本地方法要稳） |
写本地测试时，我通常还会生成一个长度为 10^5 的随机数组，同时跑暴力和贪心两个版本，先验证结果一致，再用大数组单独压测贪心版本的耗时。这样既能确认优化没改坏逻辑，也能直观感受到 O(n) 和 O(n²) 的差距。
5.3 从 121 到股票系列：为什么说它是地基
121 题是整个股票系列最简单的一道，但它定义了这个系列的状态骨架。122 题允许多次交易，需要引入“是否持有股票”的状态；123 题限制最多两笔交易，要把状态拆成第一笔买入、第一笔卖出、第二笔买入、第二笔卖出；188 题把两笔推广到 k 笔；309 题加入冷冻期；714 题加入手续费。这些题目的核心推导，都是从“某天卖出能赚多少 = 当天价格 - 历史最佳买入成本”这个公式生长出来的。
理解了 121 的从暴力到贪心，你就等于掌握了整个系列的思维起点：每道扩展题的价值，都不在于背下状态转移方程，而在于能自己推导出“新增的约束条件到底改变了哪个维护变量”。
把这道题完整吃透后，我个人的体会是：LeetCode 热题100里真正考验思维深度的，往往不是那些需要冷门算法的题，而是这种“看似简单、实际上藏着一条完整优化链路”的基础题。面试时如果被问到，你从暴力讲起，再一步步压缩到贪心，比直接甩出最优解要加分得多。这道题我后来再写，依然会先在草稿纸上列一遍暴力结构的冗余点，不是因为它快，而是因为那个过程能让我确认自己没有漏掉任何一种买卖组合。
