Best Time to Buy and Sell Stock（买卖股票的最佳时机）

题目 / Problem

中文： 给定一个数组 prices，其中 prices[i] 表示某只股票第 i 天的价格。

你只能选择某一天买入这只股票，并选择未来的另一天卖出。请计算这笔交易能够获得的最大利润。如果无法获得任何利润，返回 0。

English: You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

示例 / Examples

Example 1

Input:  prices = [7, 1, 5, 3, 6, 4]
Output: 5

解释 / Explanation:
在第 2 天以价格 1 买入，并在第 5 天以价格 6 卖出，利润为 6 - 1 = 5。
Buy on day 2 at price 1 and sell on day 5 at price 6, for a profit of 6 - 1 = 5.

不能在第 2 天买入后回到第 1 天卖出，因为必须先买入再卖出。
Buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2

Input:  prices = [7, 6, 4, 3, 1]
Output: 0

解释 / Explanation:
价格持续下降，因此不进行交易，最大利润为 0。
Prices keep decreasing, so no transaction is made and the maximum profit is 0.

约束 / Constraints

• 1 <= prices.length <= 10⁵
• 0 <= prices[i] <= 10⁴

解题思路：一次遍历 / Approach: One Pass

卖出股票时，最大利润取决于此前出现过的最低买入价格。遍历数组并维护两个变量：
When selling the stock, the maximum profit depends on the lowest price seen before that day. Traverse the array while maintaining two variables:

• minPrice：截至当前日期之前遇到的最低价格。
  minPrice: the lowest price encountered so far.
• maxProfit：截至当前日期能够获得的最大利润。
  maxProfit: the greatest profit achievable so far.

对于每天的价格 price：
For each daily price price:

1. 计算如果今天卖出，可以获得的利润 price - minPrice。
   Calculate the profit from selling today: price - minPrice.
2. 使用这个利润更新 maxProfit。
   Use this profit to update maxProfit.
3. 使用今天的价格更新最低买入价格 minPrice。
   Use today's price to update minPrice.

由于 minPrice 只来自当天或更早的价格，算法始终满足“先买入、后卖出”的要求。
Because minPrice only comes from the current or an earlier day, the algorithm always respects the requirement to buy before selling.

JavaScript 实现 / JavaScript Implementation

/**
 * @param {number[]} prices
 * @return {number}
 */
function maxProfit(prices) {
  let minPrice = Infinity;
  let maxProfit = 0;

  for (const price of prices) {
    minPrice = Math.min(minPrice, price);
    maxProfit = Math.max(maxProfit, price - minPrice);
  }

  return maxProfit;
}

执行过程 / Walkthrough

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

最低买入价格为 1，之后的最佳卖出价格为 6，所以最大利润为 5。
The lowest buying price is 1, and the best later selling price is 6, so the maximum profit is 5.

复杂度 / Complexity

• 时间复杂度：O(n)，只需遍历数组一次。
  Time: O(n), because the array is traversed once.
• 空间复杂度：O(1)，只使用两个额外变量。
  Space: O(1), because only two extra variables are used.

暴力解法对比 / Brute-Force Comparison

暴力解法枚举所有满足买入日在卖出日之前的组合，并计算每一笔交易的利润。
The brute-force approach checks every valid buy-and-sell pair and calculates its profit.

function maxProfitBruteForce(prices) {
  let maxProfit = 0;

  for (let buy = 0; buy < prices.length; buy++) {
    for (let sell = buy + 1; sell < prices.length; sell++) {
      maxProfit = Math.max(maxProfit, prices[sell] - prices[buy]);
    }
  }

  return maxProfit;
}

• 时间复杂度 / Time: O(n²)
• 空间复杂度 / Space: O(1)

当 prices.length 达到 10⁵ 时，O(n²) 的解法会超时，因此应使用一次遍历的 O(n) 解法。
When prices.length reaches 10⁵, the O(n²) approach will time out, so the O(n) one-pass solution should be used.

易错点 / Common Pitfalls

• 必须先买入再卖出，不能用未来的最低价格计算过去的卖出利润。
  You must buy before selling; do not use a future low price for an earlier selling day.
• 只允许完成一笔交易，不能累加多次价格上涨产生的利润。
  Only one transaction is allowed; do not add profits from multiple price increases.
• 当价格持续下降时，应返回 0，而不是负数。
  When prices keep decreasing, return 0 instead of a negative value.
• 返回的是最大利润，不是买入价、卖出价或日期。
  Return the maximum profit, not the buying price, selling price, or day indices.