买卖股票的最佳时机 题解

买卖股票的最佳时机

问题描述

给定一个数组 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。
  

解题思路

为了求最大利润，我们需要在买入价格最低的时候买入，并在之后价格最高的时候卖出。然而，由于我们只能遍历一次数组，并且需要在买入之后才能卖出，因此我们需要一种高效的方法来计算最大利润。

核心思想：

• 维护一个当前为止的最低买入价格 minPrice。
• 计算当前价格与最低买入价格之间的差值，即当前可获得的利润 price - minPrice。
• 维护一个最大利润值 maxProfit，在遍历过程中更新它。

算法步骤

1. 初始化：

   • minPrice = Infinity：表示当前遇到的最低价格，初始为正无穷大。
   • maxProfit = 0：表示当前计算的最大利润，初始为 0。

2. 遍历价格数组：

   对于每个价格 price，执行以下操作：

   • 更新最低价格：

     • 如果 price < minPrice，则更新 minPrice = price。

   • 计算当前利润并更新最大利润：

     • 计算当前利润 profit = price - minPrice。
     • 如果 profit > maxProfit，则更新 maxProfit = profit。

3. 返回结果：

   • 遍历完成后，maxProfit 即为所能获得的最大利润。

代码详解

function maxProfit(prices: number[]): number {let minPrice = Infinity; // 初始化最低价格为无穷大let maxProfit = 0;       // 初始化最大利润为 0for (let price of prices) {if (price < minPrice) {minPrice = price; // 更新最低价格} else if (price - minPrice > maxProfit) {maxProfit = price - minPrice; // 更新最大利润}}return maxProfit;
}

• 变量初始化：

  • minPrice：用于记录当前为止的最低买入价格。
  • maxProfit：用于记录当前为止的最大利润。

• 遍历数组：

  for (let price of prices) {...
  }
  

  • 更新最低价格：

    if (price < minPrice) {minPrice = price;
    }
    

    • 如果当前价格比之前记录的最低价格还低，更新最低价格。

  • 更新最大利润：

    else if (price - minPrice > maxProfit) {maxProfit = price - minPrice;
    }
    

    • 如果当前价格与最低价格的差值（利润）大于之前的最大利润，更新最大利润。

• 返回结果：

  return maxProfit;
  

  • 返回计算得到的最大利润。

示例演示

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

• 初始状态：

  • minPrice = Infinity
  • maxProfit = 0

• 遍历过程：

  1. price = 7：

     • 7 < Infinity，更新 minPrice = 7。
     • 没有更新 maxProfit，因为 price - minPrice = 0。

  2. price = 1：

     • 1 < 7，更新 minPrice = 1。
     • 没有更新 maxProfit，因为 price - minPrice = 0。

  3. price = 5：

     • 5 > 1，计算利润 5 - 1 = 4。
     • 4 > 0，更新 maxProfit = 4。

  4. price = 3：

     • 3 > 1，计算利润 3 - 1 = 2。
     • 2 < 4，maxProfit 不变。

  5. price = 6：

     • 6 > 1，计算利润 6 - 1 = 5。
     • 5 > 4，更新 maxProfit = 5。

  6. price = 4：

     • 4 > 1，计算利润 4 - 1 = 3。
     • 3 < 5，maxProfit 不变。

• 结果：

  • 最终 maxProfit = 5。

时间和空间复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 prices 的长度。我们只需要遍历一次数组。

• 空间复杂度：O(1)，只使用了常数级别的额外空间。

边界情况处理

• 价格单调递减：

  • 例如 prices = [7,6,4,3,1]，在这种情况下，无法获得正利润。
  • 算法会始终更新 minPrice，但 maxProfit 保持为 0。
  • 最终返回 0。

• 只有一个价格：

  • 当 prices.length == 1 时，无法完成交易，利润为 0。

测试代码

function testMaxProfit() {const testCases = [{ prices: [7, 1, 5, 3, 6, 4], expected: 5 },{ prices: [7, 6, 4, 3, 1], expected: 0 },{ prices: [1, 2], expected: 1 },{ prices: [2, 4, 1], expected: 2 },{ prices: [3], expected: 0 },];for (let { prices, expected } of testCases) {const result = maxProfit(prices);console.assert(result === expected, `测试失败：输入 ${prices}，期望输出 ${expected}，实际输出 ${result}`);}console.log("所有测试用例通过！");
}testMaxProfit();

总结

• 核心思想：在一次遍历中，找到最低的买入价格和最高的卖出价格（在买入之后）。
• 算法优势：时间复杂度低，只需要遍历一次数组，空间复杂度为 O(1)。
• 注意事项：在更新 minPrice 时，只更新更低的价格；在计算利润时，必须确保当前价格是在 minPrice 之后的。