leetcode with python:121. Best Time to Buy and Sell Stock

题目:

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

给定一阵列纪录每天股票的价钱,回传在最好时机买卖股票(买一天,卖一天)能获得的最大获利
ex:input:[7,1,5,3,6,4]=>output:5
explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

我对这题的想法很像53.的法二

class Solution:    def maxProfit(self, prices: List[int]) -> int:        ans=0        buy=prices[0]        for i in prices:            buy=min(buy,i)            ans=max(ans,i-buy)        return ans

从prices[0]开始用buy纪录最低买价
只需要考虑(buy之后价位-buy)的可能
因为当找到比更低的价格的时候
就不用考量以之前纪录的更高价钱买入后以同样价钱卖出的可能了(获利必然较小)
且我们不能穿越时空(第三日股票在第一日卖出)
所以我们让buy从第一项遍历,一旦出现比buy还小的价格就替换
中途纪录获利(当日价格-buy)最大值
以O(n)遍历了所有可能为最大获利的可能
然后只要回传纪录到的获利最大值即可
最后执行时间1073ms(faster than 92.30%)

那我们下题见