题目

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。

示例1

  1. 输入: [7,1,5,3,6,4]
  2. 输出: 5
  3. 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
  4.      注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

实现

思路1 暴力解法

两重循环遍历所有的买入卖出方案，找到获利最高的方案即可。但该方法会超时。

  1. class Solution:
  2.     def maxProfit(self, prices: List[int]) -> int:
  3.         ans = 0
  4.         for i in range(len(prices)):
  5.             for j in range(i + 1, len(prices)):
  6.                 ans = max(ans, prices[j] - prices[i])
  7.         return ans

思路2

对思路1进行优化，减小时间复杂度，使用一次循环解决。
方法是使用一个变量记录最低价格，一个变量记录最大利润值。假设是在最低价格当天买入，之后在该最低价格后的时间区间内遍历，计算当天卖出的利润，然后更新记录的最大利润值。这样一次遍历就可以解决。

  1. class Solution:
  2.     def maxProfit(self, prices: List[int]) -> int:
  3.         minprice = float("inf")
  4.         maxprofit = 0
  5.         for price in prices:
  6.             maxprofit = max(price-minprice, maxprofit)
  7.             minprice = min(price, minprice)
  8.         return maxprofit

时间复杂度：。只需要一次遍历
空间复杂度：121. 买卖股票的最佳时机 - 图1。