买卖股票最佳时机

问题

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

你只能选择某一天买入，并在未来的某一天卖出。计算你能获取的最大利润。如果无法获利，返回 0。

输入: [7, 1, 5, 3, 6, 4]
输出: 5
解释: 第 2 天买入(价格 1)，第 5 天卖出(价格 6)，利润 = 6 - 1 = 5

解答

一次遍历

/**
 * 买卖股票的最佳时机
 * @param {number[]} prices - 股票价格数组
 * @return {number} 最大利润
 */
function maxProfit(prices) {
  if (prices.length < 2) return 0;

  let minPrice = prices[0]; // 记录遍历过程中的最低价格
  let maxProfit = 0; // 记录最大利润

  for (let i = 1; i < prices.length; i++) {
    // 如果当前价格更低，更新最低价格
    if (prices[i] < minPrice) {
      minPrice = prices[i];
    } else {
      // 否则计算以当前价格卖出的利润，更新最大利润
      maxProfit = Math.max(maxProfit, prices[i] - minPrice);
    }
  }

  return maxProfit;
}

// 测试
console.log(maxProfit([7, 1, 5, 3, 6, 4])); // 5
console.log(maxProfit([7, 6, 4, 3, 1])); // 0 (价格一直下跌，无法获利)
console.log(maxProfit([2, 4, 1])); // 2

简化写法

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;
}

动态规划思路

/**
 * dp[i] 表示第 i 天卖出能获得的最大利润
 * dp[i] = max(dp[i-1] + prices[i] - prices[i-1], 0)
 */
function maxProfit(prices) {
  let dp = 0; // 空间优化，只保留前一天的状态
  let maxProfit = 0;

  for (let i = 1; i < prices.length; i++) {
    // 今天卖出的利润 = 昨天卖出的利润 + 今天与昨天的差价
    // 如果为负，说明应该今天买入，重置为 0
    dp = Math.max(0, dp + prices[i] - prices[i - 1]);
    maxProfit = Math.max(maxProfit, dp);
  }

  return maxProfit;
}

关键点

• 只需遍历一次，时间复杂度 O(n)，空间复杂度 O(1)
• 核心思路：遍历时记录最低买入价，计算当前卖出的利润
• 买入必须在卖出之前，所以从左到右遍历时，最低价一定在当前价格之前
• 如果价格一直下跌，最大利润为 0（不交易）
• 动态规划思路：将问题转化为求最大连续子数组和