題目:

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%)

那我們下題見