我来给你讲解 LeetCode 第 121 题「买卖股票的最佳时机」。

题目描述

给定一个数组 prices，其中 prices[i] 表示股票在第 i 天的价格。你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

如果你不能获取任何利润，返回 0。

示例 1：

输入: prices = [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（价格 = 1）买入，在第 5 天（价格 = 6）卖出，利润 = 6-1 = 5。

示例 2：

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

解题思路

第一步：理解问题本质

这个问题要求我们找到一对 (i, j)，其中 i < j，使得 prices[j] - prices[i] 的值最大。换句话说，我们要找到最低的买入价格和最高的卖出价格，且卖出必须在买入之后。

第二步：暴力解法（理解基础逻辑）

最直观的想法是尝试所有可能的买入和卖出组合：

def maxProfit(prices):
    max_profit = 0
    n = len(prices)
    
    for i in range(n):  # 遍历所有可能的买入时机
        for j in range(i + 1, n):  # 遍历所有可能的卖出时机（在买入之后）
            profit = prices[j] - prices[i]
            if profit > max_profit:
                max_profit = profit
    
    return max_profit

时间复杂度： O(n²) - 对于每个买入点，都要遍历所有后续的卖出点
空间复杂度： O(1)

这种方法虽然正确，但对于大数据量会超时。

第三步：优化思路 - 一次遍历

关键观察：对于第 i 天，如果我们想要在这天卖出股票，那么应该在 前 i-1 天中的最低价格 买入。

因此，我们可以：

1. 维护一个变量记录 至今为止遇到的最低价格
2. 对于每一天，计算 如果今天卖出，能获得的最大利润
3. 更新全局最大利润

第四步：详细算法步骤

1. 初始化 min_price 为第一天的价格
2. 初始化 max_profit 为 0
3. 从第二天开始遍历价格数组：
   • 计算如果今天卖出：profit = prices[i] - min_price
   • 如果 profit > max_profit，更新 max_profit
   • 如果 prices[i] < min_price，更新 min_price
4. 返回 max_profit

第五步：完整代码实现

def maxProfit(prices):
    if not prices:
        return 0
    
    min_price = prices[0]  # 记录最低买入价格
    max_profit = 0         # 记录最大利润
    
    for i in range(1, len(prices)):
        # 如果今天卖出，能赚多少钱？
        profit = prices[i] - min_price
        
        # 更新最大利润
        if profit > max_profit:
            max_profit = profit
        
        # 更新最低价格
        if prices[i] < min_price:
            min_price = prices[i]
    
    return max_profit

第六步：示例推演

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

最终结果：5

第七步：复杂度分析

• 时间复杂度： O(n) - 只需要遍历数组一次
• 空间复杂度： O(1) - 只使用了常数级别的额外空间

第八步：边界情况处理

• 空数组：直接返回 0
• 价格一直下跌：最大利润为 0（不交易）
• 只有一天价格：无法完成交易，利润为 0

这个算法巧妙地利用了"贪心"思想，在遍历过程中不断更新最低价格和最大利润，用一次遍历就解决了问题。