LeetCode 筆記 - 122. Best Time to Buy and Sell Stock II

Posted on

題目在此 122. Best Time to Buy and Sell Stock II

解題思維

這題的關鍵在於理解我們可以在同一天內進行多次買賣操作，並且可以在任何時間點買入或賣出股票。這意味著我們只需要關注價格的上升趨勢，並在每次價格上升時進行買賣操作以獲取利潤。
我們可以遍歷價格陣列，並在每次發現當天的價格高於前一天的價格時，將這部分的利潤加入總利潤中。這樣，我們就能夠捕捉到所有的上升趨勢，從而最大化總利潤。

Time complexity 是 $O(n)$，因為我們只需要遍歷價格陣列一次。
Space complexity 是 $O(1)$，因為我們只使用了常數級別的額外空間來存儲利潤。

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def maxProfit(self, prices: List[int]) -> int:

        # step 0: walk the prices
        # step 1: if we found out today's price can make some profit: do it!!!

        # time complexity: O(n)
        # space complexity: O(1)

        profit = 0
        pre_p = None

        for p in prices:
            if pre_p is not None and p - pre_p > 0:
                profit += p - pre_p
            pre_p = p
            
        return profit

也許你也會想看看