#买卖股票的最佳时机

#题目描述

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

#思路分析

这道题的关键在于：我们要找到一对 (买入日, 卖出日)，使得 prices[卖出日] - prices[买入日] 最大，且卖出日必须在买入日之后。

最朴素的做法是两层循环枚举所有买卖组合，时间复杂度为 O(n²)，当数据量较大时效率不理想。

更高效的思路是 一次遍历。我们从左到右扫描价格数组，在遍历的过程中始终维护一个 历史最低价格 minPrice。对于当天的价格，如果它比 minPrice 还低，就更新 minPrice；否则，用当天价格减去 minPrice 就得到了"假如今天卖出"的利润，再与已记录的最大利润做比较，取较大值即可。这种贪心策略之所以有效，是因为最大利润一定产生在某个最低点之后的某个最高点，而我们在遍历时恰好同时追踪了这两个信息。

#示例代码

/**
 * @param prices - 每日股票价格数组
 * @returns 最大利润，无法获利时返回 0
 *
 * @example
 * maxProfit([7, 1, 5, 3, 6, 4]) // 5  （第2天买入，第5天卖出）
 * maxProfit([7, 6, 4, 3, 1])    // 0  （价格持续下跌，无法获利）
 */
export function maxProfit(prices: number[]): number {
  // 记录遍历过程中的最大利润
  let profit = 0;

  // 记录遍历过程中遇到的最低价格，初始为第一天的价格
  let minPrice = prices[0];

  // 从第二天开始遍历
  for (let i = 1; i < prices.length; i++) {
    if (prices[i] < minPrice) {
      // 发现更低的买入价格，更新 minPrice
      minPrice = prices[i];
    } else {
      // 以当前价格卖出，计算利润并与历史最大利润比较
      profit = Math.max(profit, prices[i] - minPrice);
    }
  }

  return profit;
}

#复杂度分析

• 时间复杂度：O(n)，其中 n 为数组长度。只需一次遍历，每个元素仅被访问一次。
• 空间复杂度：O(1)。只使用了 profit 和 minPrice 两个辅助变量，与输入规模无关。

#示例演示

以 prices = [7, 1, 5, 3, 6, 4] 为例，核心步骤如下：

1. 第 0 天价格为 7，初始化 minPrice = 7。
2. 第 1 天价格为 1，比 minPrice 低，更新 minPrice = 1。
3. 第 2 天价格为 5，利润为 5 - 1 = 4，更新最大利润为 4。
4. 第 3 天价格为 3，利润为 3 - 1 = 2，不超过 4，最大利润不变。
5. 第 4 天价格为 6，利润为 6 - 1 = 5，更新最大利润为 5。
6. 第 5 天价格为 4，利润为 4 - 1 = 3，不超过 5，最大利润不变。

最终结果为 5，即第 1 天买入（价格 1），第 4 天卖出（价格 6）。