0121. Best Time to Buy and Sell Stock - chasel2361/leetcode GitHub Wiki

Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.

Example 1:
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.
Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

這個題目主要的目的是找出最大的獲利，需要注意的地方是股價買進的高點不能在賣出低點之前出現，這樣的話可以利用指標的概念，算出指標處之累積獲利是否比最大獲利還大，若是則更新最大獲利，若否則指標前進，寫作程式碼如下：

[1] profit除了為當前指標處與前一天股價相減所得獲利之外，還需要加上前一天之累積獲利，並且必須大於零

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit, maxprofit = 0, 0        
        for i in range(1, len(prices)):
            profit = max(0, prices[i] - prices[i-1] + profit) #[1]
            maxprofit = max(profit, maxprofit)
        return profit

這樣寫的時間複雜度是O(N)，空間複雜度是O(2)

同樣概念，我們可以加入判斷讓減少無謂的計算，只有當前累積獲利大於最大獲利才更新

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices: return 0
        maxprofit, minprice = 0, prices[0]
                    
        for p in prices[1:]:
            profit = p - minprice
            if profit > maxprofit:
                maxprofit = profit
            elif profit < 0:
                minprice = p
        return maxprofit

如此雖然時間複雜度與空間複雜度與前者相同，計算時間可以明顯下降(72ms→60ms)