LeetCode:(Python)(Array) Best Time to Buy and Sell Stock

題目連結: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/?envType=study-plan-v2&envId=top-interview-150

題意說明:

• prices 這個 list中的數字代表從第一天開始每一天的股價。
• 要找出最大的收益

注意事項:

• 因為時間不可逆，我們只能在購買之後的時間點賣出，如果購買後一直跌，那獲益是負值，return 0

實作程式碼

• 想像一下，在每一個時間點，我們都能看到之前的所有價格，也能找到最小的購買價格
• 當目前的價格小於歷史最低購買價格時，更新歷史最低購買價格
• 當目前的價格 - 歷史最低購買價格的獲益，比歷史最高獲益更高，更新歷史最高獲益

每一次最低購買價格更新，都只能被更之後的價格使用於計算最大獲益。

每一次當下的價格 - 最低購買價格 > 最大獲益，就更新最大獲益

prices = [7,1,5,3,6,4]
#1 最低購買價格: 7, 最大獲益: 7 - 最低購買價格 = 7 - 7 =0
#2 最低購買價格: 1, 最大獲益: 1 - 最低購買價格 = 1 - 1 = 0
#3 最低購買價格: 1, 最大獲益: 5 - 最低購買價格 = 5 - 1 = 4
#4 最低購買價格: 1, 最大獲益: 4，因為 #3 的4 >3 - 最低購買價格 = 3 - 1 = 2
#4 最低購買價格: 1, 最大獲益: 6- 最低購買價格 = 6- 1 = 5
. . . 

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = float('inf')  # 初始化一個極大值，表示最小的價格
        profit = 0  # 初始化最大利潤為0

        for price in prices:
            if price < min_price:
                min_price = price  # 更新到目前為止的最小價格
            elif price - min_price > profit: 
            # 用 if也可以，但如果第一個 if剛剛成立，min_price會等於目前的 price
            # 這時再計算 price - min_price 必然 = 0，意義不大
                profit = price - min_price  # 更新最大利潤
                
        return profit