LeetCode 121股票买卖问题：O(n)解法与优化思路

1. LeetCode 121 题目解析与核心思路

这道题目要求我们在给定的股票价格序列中，找到一次买入和卖出的最佳时机，使得利润最大化。输入是一个数组prices，其中prices[i]表示第i天股票的价格。我们需要返回能够获得的最大利润。如果无法获得正利润，则返回0。

1.1 问题本质与数学模型

这道题本质上是一个序列极值问题。我们需要找到两个点i和j（i < j），使得prices[j] - prices[i]的值最大化。用数学表达式可以表示为：

max_profit = max(prices[j] - prices[i])，其中0 ≤ i < j < n

直接暴力解法是枚举所有可能的i和j组合，计算每种情况下的利润并记录最大值。这种方法的时间复杂度是O(n²)，对于较大的n（比如n=10^5）来说效率太低。

1.2 关键观察与优化思路

通过分析我们可以发现一个关键性质：对于任意一天j，如果我们想在j天卖出股票，那么最优的买入价格应该是前j-1天中的最低价格。因此，我们可以在遍历数组时：

1. 记录当前遇到的最小价格min_price
2. 计算当前价格与min_price的差值作为潜在利润
3. 更新最大利润max_profit

这种单次遍历的方法将时间复杂度降低到了O(n)，空间复杂度为O(1)，是非常高效的解决方案。

2. 详细解法与代码实现

2.1 Python实现与逐行解析

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

代码解析：

1. 初始化min_price为正无穷大，确保第一个价格一定会更新min_price
2. 初始化max_profit为0，对应无法获利的情况
3. 遍历价格数组：
   • 如果当前价格比min_price小，更新min_price
   • 否则计算当前利润，如果大于max_profit则更新
4. 最后返回max_profit

2.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; }

Java版本与Python思路完全一致，主要区别在于：

• 使用Integer.MAX_VALUE代替float('inf')
• 强类型语言需要声明变量类型
• 数组遍历语法略有不同

2.3 边界条件处理

这道题有几个需要注意的边界情况：

1. 空数组或单元素数组：直接返回0
2. 价格持续下跌：最大利润为0
3. 价格持续上涨：最大利润为最后一天减第一天
4. 价格波动：需要正确识别最低点和后续最高点

我们的解法已经天然处理了这些边界情况：

• 初始max_profit=0保证了无利润时返回0
• min_price的更新机制确保总能找到历史最低点
• 单次遍历确保不会出现i>j的情况

3. 算法复杂度分析与优化证明

3.1 时间复杂度证明

算法只对价格数组进行一次遍历，每个元素只被访问一次，没有嵌套循环。因此时间复杂度显然是O(n)，其中n是数组长度。

3.2 空间复杂度证明

算法只使用了固定数量的额外变量（min_price和max_profit），不随输入规模变化。因此空间复杂度是O(1)。

3.3 最优性证明

我们可以用反证法证明这个解法的最优性：

假设存在一个更优的解，即在某一天j卖出时，买入点i不是前j-1天的最低点。那么必然存在某天k（i < k < j）使得prices[k] < prices[i]。此时选择在k点买入会获得更大利润prices[j] - prices[k]，与假设矛盾。因此我们的解法确实能找到全局最优解。

4. 变种问题与扩展思考

4.1 允许多次交易的情况

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 最多完成两笔交易

LeetCode 123题进一步限制最多完成两笔交易。这需要更复杂的动态规划解法，分别记录第一次和第二次交易的最大利润。

4.3 含冷冻期的情况

LeetCode 309题引入了卖出后需要等待一天冷冻期的限制。这类问题通常需要状态机DP来解决，区分持有股票、不持有且在冷冻期、不持有且不在冷冻期三种状态。

5. 实际面试中的技巧与注意事项

5.1 面试解题步骤建议

1. 先明确问题要求，确认输入输出格式
2. 提出暴力解法并分析复杂度
3. 寻找优化空间，提出关键观察点
4. 写出优化后的伪代码
5. 实现完整代码
6. 测试边界条件
7. 分析时间空间复杂度

5.2 常见错误与避免方法

1. 混淆买入卖出顺序：确保卖出日在买入日之后
2. 初始化不当：min_price应初始化为极大值，max_profit初始化为0
3. 更新顺序错误：应先检查是否需要更新min_price，再计算利润
4. 数组越界：处理空数组或单元素数组情况

5.3 面试官可能追问的问题

1. 如何修改算法以同时返回买入和卖出日期？
   • 需要额外记录min_price出现的位置
2. 如果允许做空（先卖后买）会怎样？
   • 问题性质完全改变，需要找最大跌幅
3. 如何应对实时数据流场景？
   • 维护当前min和max_profit，每来一个新数据就更新

6. 实际应用场景延伸

虽然题目设定是股票交易，但这个算法模式可以应用于许多类似场景：

1. 商品价格波动中的最佳买卖时机
2. 资源分配中的最佳投入产出时间点
3. 时间序列数据分析中的极值点识别
4. 生产计划中的最佳原材料采购时机

在量化交易中，这种寻找价格极值的模式是许多交易策略的基础。虽然真实的股票交易要考虑更多因素（如手续费、滑点等），但核心思路是相通的。

7. 不同语言实现的性能对比

在实际运行时，不同语言的实现会有性能差异：

测试数据为10^5个随机价格数据，取平均值。虽然算法复杂度相同，但常数因子差异明显。

8. 算法可视化与理解技巧

为了更好理解这个算法，可以想象一个价格折线图：

1. 随着时间推移，价格曲线上上下下
2. 我们维护一个"历史最低点"指针
3. 每到一个新点，计算与历史最低点的差值
4. 如果发现更低的点，就移动指针
5. 始终保持记录最大的差值

这种可视化方法可以帮助理解为什么只需要一次遍历就能找到最优解，而不需要比较所有可能的组合。

9. 刷题建议与学习路径

对于想要系统学习算法题的同学，建议：

1. 先掌握基础数据结构：数组、链表、哈希表、栈、队列
2. 学习基本算法思想：贪心、分治、回溯、动态规划
3. 按类型刷题，比如先集中解决数组相关题目
4. 每道题多思考不同解法，比较优缺点
5. 定期复习经典题目，如本题就是必须掌握的经典

这道股票买卖问题是一个系列，建议按顺序解决： 121 → 122 → 123 → 188 → 309 → 714 难度逐步提升，解法也越来越复杂。