121_买卖股票的最佳时机

类型：数组

• 121. 买卖股票的最佳时机 💚

  https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

  ❓ 数组 prices 表示股票在每天的价格，只能在某一天买入，某一天卖出。求最大收益。

  💡 一次遍历

  我们遍历的数组，考虑在当天卖出股票可获得的最大收益，为 prices[i] - minPrice.

  因此我们只需要遍历一次数组，并实时维护当前历史最低价。

  class Solution:
      def maxProfit(self, prices: List[int]) -> int:
          inf = int(1e9)
          minprice = inf
          maxprofit = 0
          for price in prices:
              maxprofit = max(price - minprice, maxprofit)
              minprice = min(price, minprice)
          return maxprofit

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