好的，我们这次来详细讲解 LeetCode 第 121 题「买卖股票的最佳时机」。

1. 题目描述

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

示例 1：

输入: prices = [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（价格 = 1）买入，在第 5 天（价格 = 6）卖出，利润 = 6 - 1 = 5。
     注意利润不能是 7 - 1 = 6，因为卖出价格需要大于买入价格；同时你不能在买入前卖出。

示例 2：

输入: prices = [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

约束条件：

• 1 <= prices.length <= 10^5
• 0 <= prices[i] <= 10^4

2. 题意理解与思路分析

关键点

• 只能买卖一次（先买后卖，各一次）。
• 买必须在卖之前（按时间顺序）。
• 目标是 卖出价格 - 买入价格 最大。
• 如果价格一直下跌，则利润为 0（不交易）。

暴力法思路（会超时）

我们可以枚举所有可能的买入天和卖出天组合（卖出天在买入天之后），计算利润，取最大值。
伪代码：

max_profit = 0
for i = 0 to n-1:
    for j = i+1 to n-1:
        profit = prices[j] - prices[i]
        if profit > max_profit:
            max_profit = profit

时间复杂度 O(n²)，在 n 最大 10^5 时会超时。

3. 优化思路：一次遍历（动态规划思想）

我们想要的是：
最大利润 = max( prices[j] - prices[i] )，其中 j > i。

换个角度：
如果我们固定 j（卖出的日子），那么对于这一天来说，最大利润 = prices[j] - min_price_so_far，其中 min_price_so_far 是第 j 天之前的 最低价格（即买入价格）。

所以算法步骤：

1. 初始化 min_price 为第一天的价格（或一个很大的数）。
2. 初始化 max_profit = 0。
3. 遍历每一天的价格 price：
   • 计算如果今天卖出：profit = price - min_price
   • 更新 max_profit = max(max_profit, profit)
   • 更新 min_price = min(min_price, price)（为后续日子准备）
4. 返回 max_profit。

4. 逐步推导示例

以 prices = [7, 1, 5, 3, 6, 4] 为例：

最终结果：5。

5. 代码实现（Python）

def maxProfit(prices):
    if not prices:
        return 0
    
    min_price = prices[0]
    max_profit = 0
    
    for price in prices:
        # 计算今天卖出的利润
        profit = price - min_price
        # 更新最大利润
        if profit > max_profit:
            max_profit = profit
        # 更新最低价格
        if price < min_price:
            min_price = price
    
    return max_profit

6. 复杂度分析

• 时间复杂度：O(n)，只需一次遍历。
• 空间复杂度：O(1)，只用了几个变量。

7. 总结与扩展

• 本题核心是 维护一个历史最低价，然后每天考虑在该历史最低价买入、当天卖出的利润。
• 这是股票买卖系列中最简单的一题，后续还有可以多次买卖、含冷冻期、含手续费等变种，但思路都从此基础演变。
• 关键思维：将问题转化为“对于每个卖出日，找到之前的最低买入价”，从而避免 O(n²) 的枚举。

这样讲解是否清晰？我们可以继续练习类似思路的题目，比如 买卖股票的最佳时机 II（可多次买卖）。