𝗟𝗲𝗲𝘁𝗰𝗼𝗱𝗲 𝟭𝟱𝟬 | 𝗗𝗮𝘆 𝟱: 𝗕𝗲𝘀𝘁 𝗧𝗶𝗺𝗲 𝘁𝗼 𝗕𝘂𝘆 𝗮𝗻𝗱 𝗦𝗲𝗹𝗹 𝗦𝘁𝗼𝗰𝗸

Leetcode 121 要求你找到买卖股票的最佳时机。你会得到一个价格数组。每个索引代表一天，数组中的值是那一天的价格。

目标很简单：在某一天买入，并在未来的某一天卖出，以获得最大利润。如果无法获利，则返回 0。

问题约束：

  • 数组长度最高为 100,000。
  • 价格最高为 10,000。
  • 你必须在买入之后才能卖出。

方法 1：朴素法（暴力破解）

暴力破解法会检查每一对买入和卖出的组合。这需要使用两层循环。

  • 时间复杂度：O(n²)
  • 问题：速度太慢。

如果你有 1,000 天，你需要进行 1,000,000 次检查。如果有 100,000 天，你需要进行 10,000,000,000 次检查。这会导致在 Leetcode 上超时。

方法 2：优化法（一次遍历）

你可以使用两个变量 minPrice 和 maxProfit 通过一次遍历来解决这个问题。

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

工作原理：

  1. 将 minPrice 设置为无穷大 (Infinity)。
  2. 将 maxProfit 设置为 0。
  3. 遍历每个价格。
  4. 如果当前价格低于 minPrice，则更新 minPrice。
  5. 如果当前价格减去 minPrice 的值大于 maxProfit，则更新 maxProfit。

价格为 [7, 1, 5, 3, 6, 4] 的示例追踪：

  • 第 1 天：价格 7。minPrice 变为 7。maxProfit 保持为 0。
  • 第 2 天：价格 1。minPrice 变为 1。maxProfit 保持为 0。
  • 第 3 天：价格 5。5 - 1 = 4。maxProfit 变为 4。
  • 第 4 天：价格 3。3 - 1 = 2。maxProfit 保持为 4。
  • 第 5 天：价格 6。6 - 1 = 5。maxProfit 变为 5。
  • 第 6 天：价格 4。4 - 1 = 3。maxProfit 保持为 5。

最终答案：5。

优化版本之所以胜出，是因为它只需查看每个价格一次。它在处理大规模数据集时表现出色。

来源：https://dev.to/afuji/leetcode-150-day-5-best-time-to-buy-and-sell-stock-naive-vs-optimized-4mk1