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(i+1, 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 算法正确性证明

为什么这种方法能保证找到最大利润？因为：

1. 我们始终记录着到当前为止的最低买入价
2. 每次遇到更高的价格时，都计算可能的利润
3. 只保留最大的利润值

这样就能确保不会错过任何可能的更高利润组合。

3. 边界条件与特殊测试用例

3.1 常见边界情况

1. 价格持续下跌：[7,6,4,3,1] → 应返回0（不交易）
2. 空数组：[] → 应返回0
3. 单元素数组：[7] → 应返回0
4. 价格相同：[2,2,2,2] → 应返回0

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

4.2 类似问题扩展

1. 允许多次交易（LeetCode 122）
2. 最多两次交易（LeetCode 123）
3. 最多k次交易（LeetCode 188）
4. 含冷冻期（LeetCode 309）

5. 实际应用场景

这类算法问题虽然简单，但在实际金融交易系统中非常重要：

1. 高频交易系统需要实时计算最佳买卖点
2. 量化投资策略中的趋势判断
3. 投资组合优化

6. 常见错误与调试技巧

6.1 新手常见错误

1. 忘记初始化min_price为极大值
2. 将max_profit初始化为负值（应为0）
3. 混淆买入和卖出的时间顺序

6.2 调试建议

1. 打印每次循环的min_price和max_profit
2. 用简单测试用例手动验证
3. 特别注意数组为空或单元素的情况

7. 性能分析与比较

7.1 时间复杂度对比

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_profit

8.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 面试官可能追问的问题

1. 如何证明你的算法是正确的？
2. 如果允许多次交易怎么做？
3. 如果交易有手续费怎么处理？
4. 如何扩展到多支股票？

9.2 回答策略建议

1. 先给出暴力解法，再优化
2. 主动讨论时间/空间复杂度
3. 提出测试用例
4. 讨论可能的扩展

10. 学习资源推荐

1. 《算法导论》动态规划章节
2. LeetCode股票买卖问题系列（121-188题）
3. 《编程珠玑》中的算法优化思想
4. 极客时间的算法面试精讲课程

在实际刷题过程中，我发现很多同学容易忽视边界条件的检查。比如当输入数组为空时直接开始计算，导致运行时错误。建议养成先检查输入有效性的习惯，这在面试中也是加分项。