LeetCode股票买卖问题：一次遍历法求最大利润

1. 问题背景与核心理解

这道题目来自力扣（LeetCode）第121题，是算法面试中的经典问题。题目描述很简单：给定一个数组prices，其中prices[i]表示某支股票第i天的价格。你只能选择某一天买入这只股票，并在未来某个不同的日子卖出。要求计算你能获得的最大利润。

我第一次看到这个问题时，直觉反应是"这不就是找数组中的最大差值吗？"。但实际解题时发现没那么简单，因为卖出的日期必须晚于买入日期。举个例子：

给定价格序列[7,1,5,3,6,4] 如果我们在第2天买入（价格1），第5天卖出（价格6），利润为5（6-1=5）就是最大利润。其他任何买卖组合都无法获得更高利润。

2. 暴力解法与优化思路

2.1 直观的暴力解法

最直接的思路是双重循环：外层循环遍历所有可能的买入点，内层循环遍历该买入点之后的所有卖出点，计算利润并记录最大值。

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

这个解法的时间复杂度是O(n²)，在力扣上提交会超时（当n=10⁵时）。我在实际测试时发现，当价格序列长度超过10000时，运行时间就明显变慢了。

2.2 寻找优化方向

观察问题特点可以发现：

1. 我们只需要知道最大利润，不需要知道具体哪天买卖
2. 最大利润取决于最低买入价和最高卖出价（且卖出在买入之后）
3. 可以在一次遍历中同时跟踪最低价和最大利润

3. 最优解法：一次遍历法

3.1 算法思路

维护两个变量：

• min_price：遍历过程中遇到的最低价格
• max_profit：当前能获得的最大利润

遍历价格数组时：

1. 如果当前价格比min_price小，更新min_price
2. 否则计算当前价格与min_price的差值，如果大于max_profit则更新

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

3.2 复杂度分析

• 时间复杂度：O(n)，只需一次遍历
• 空间复杂度：O(1)，只用了常数个额外空间

这个解法在力扣上运行时间可以击败99%的提交，实测对于长度为10⁶的数组也能在毫秒级完成。

4. 边界情况与测试用例

4.1 常见边界情况

1. 价格持续下跌：[7,6,4,3,1] → 最大利润为0（不交易）
2. 空数组：[] → 返回0
3. 单元素数组：[7] → 返回0
4. 价格波动：[2,4,1] → 最大利润为2（第1天买，第2天卖）
5. 价格相同：[3,3,3,3] → 返回0

4.2 测试代码示例

def test_maxProfit(): assert maxProfit([7,1,5,3,6,4]) == 5 assert maxProfit([7,6,4,3,1]) == 0 assert maxProfit([]) == 0 assert maxProfit([7]) == 0 assert maxProfit([2,4,1]) == 2 assert maxProfit([3,3,3,3]) == 0

5. 算法扩展与变种

5.1 允许多次交易的情况

如果允许在同一天卖出后立即买入（即可以进行多次交易），问题就变成了力扣第122题。解法思路完全不同：只要今天比昨天价格高，就把这个差值加入利润。

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

5.2 含冷冻期的情况

力扣第309题增加了冷冻期限制：卖出股票后第二天不能买入。这类问题通常需要用动态规划来解决，维护多个状态（持有、不持有在冷冻期、不持有不在冷冻期）。

6. 实际应用与面试技巧

6.1 实际应用场景

这个算法虽然简单，但在量化交易中有实际应用。比如：

• 寻找最佳买卖点时可以参考类似思路
• 可以作为更复杂交易策略的基础组件
• 用于快速评估某支股票的历史波动情况

6.2 面试常见问题

面试官可能会追问：

1. 如果要求输出买卖日期而不仅是利润，如何修改代码？
2. 如果交易需要手续费怎么处理？
3. 如何证明你的解法是最优的？

对于问题1，可以在遍历时额外记录买卖日期：

def maxProfit_with_dates(prices): min_price = float('inf') max_profit = 0 buy_day = sell_day = 0 for i, price in enumerate(prices): if price < min_price: min_price = price buy_day = i elif price - min_price > max_profit: max_profit = price - min_price sell_day = i return (max_profit, buy_day, sell_day) if max_profit > 0 else (0, -1, -1)

7. 性能优化与语言实现

7.1 Python实现优化技巧

1. 使用内置函数：在Python中，min()和max()函数实际上比手动比较慢，因为要处理更多通用情况
2. 避免不必要的变量：如上面的解法已经很精简
3. 使用numpy数组处理大数据量时可能更快

7.2 其他语言实现要点

在C++中要注意：

• 初始化min_price可以用INT_MAX
• 遍历时使用索引还是迭代器取决于具体情况

Java实现时：

• 使用Integer.MAX_VALUE初始化min_price
• 注意数组边界检查

8. 常见错误与调试技巧

8.1 新手常见错误

1. 搞错买卖顺序：先卖后买
2. 忽略价格持续下跌的情况
3. 数组越界：特别是在处理空数组或单元素数组时
4. 初始化值设置不当：如min_price初始值不够大

8.2 调试建议

1. 先用小测试用例手动验证
2. 打印中间变量值：

print(f"Day {i}: price={price}, min_price={min_price}, max_profit={max_profit}")

3. 对于边界情况单独测试

9. 算法可视化理解

为了更好理解这个算法，可以想象我们在遍历价格序列时：

• 始终拿着一个"望远镜"在寻找后面的最高峰
• 同时手里记录着目前为止见过的最低谷
• 每看到一个更低的山谷就移动我们的基准点
• 每看到一个更高的山峰就计算它与当前基准的高度差

这种"低谷+高峰"的追踪方式正是该算法高效的关键。

10. 进阶学习建议

如果想进一步掌握这类问题：

1. 完成力扣上所有股票买卖系列问题（共6题）
2. 学习动态规划在交易策略中的应用
3. 研究滑动窗口算法的其他应用场景
4. 尝试用这个算法分析真实股票数据

我在实际刷题中发现，这类问题往往有多种解法，但最优解通常都能将时间复杂度降到O(n)。关键在于发现问题的特殊性质，避免不必要的计算。