121. 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入：[7,1,5,3,6,4]
输出：5

示例 2：

输入：prices = [7,6,4,3,1]
输出：0

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        res = 0
        i = 0
        while i<len(prices):
            for j in range(i,len(prices)):
                if prices[i]<prices[j]:
                    if prices[j]-prices[i]>res:
                        res = prices[j]-prices[i]
            i += 1
        return res

两层循环，果然超出时间限制了

那怎么办了？想一想

如果找出最小的一个值那就好了

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        res = 0
        a = float('inf')
        i = 0
        while i<len(prices):
            if prices[i]<a:
                a = prices[i]
            elif prices[i]-a>res:
                res = prices[i]-a
            i += 1
        return res

代码如上，但是我起初想的是找出最小的一个值，然后在该值的后面找到一个最大的值相减就是我们要的结果，跑了一下发现不对。

后来想了一下确实不行，于是改成上面的了。