題目

  • 題目連結
  • 目標函式 : maxProfit(prices)
    • Input : prices: List[int]
    • Output : int

解題概念

  • 題意 : 給予一陣列 prices，其中 prices[i] 代表股票第 i 天的價格
  • 需要選其中一天來買進，另外一天來賣出，題目結果為本次交易的最大利潤

我的寫法

  • 想法 : 使用 for 迴圈去瀏覽每個元素
    1. 如果要找出最大利潤值，首先要找出 prices 的最小值作為買進點
    2. 如果發現 price[i] - buy > max_profit，則將該值設為 max_profit
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    def maxProfit(self, prices):
        buy = prices[0]
        max_profit = 0

        for price in prices:
            if price < buy:
                buy = price
            
            if price - buy > max_profit:
                max_profit = price - buy

        return max_profit
  • 成效 :
    • Time Complexity : $\color{DB4D6D}{O(n)}$
    • Runtime: 821 ms (faster than 93.80%)
    • Memory Usage: 22.5 MB (more than 86.85%)

解答 or 其他優秀寫法

  • 想法 : 基本上與我的想法相同，只有有些寫法是改用 while 迴圈和雙重指標去執行 searching