leetcode 121.best-time-to-buy-and-sell-stock 買賣股票的最佳時機 python3

時間：2020-5-16

題目位址：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/description/

題目難度：Easy

題目描述：

給定一個數組，它的第 i 個元素是一支給定股票第 i 天的價格。

如果你最多隻允許完成一筆交易（即買入和賣出一支股票一次），設計一個算法來計算你所能擷取的最大利潤。

注意：你不能在買入股票前賣出股票。

示例 1:

輸入: [7,1,5,3,6,4]

輸出: 5

解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 = 6）的時候賣出，最大利潤 = 6-1 = 5 。

     注意利潤不能是 7-1 = 6, 因為賣出價格需要大于買入價格；同時，你不能在買入前賣出股票。

示例 2:

輸入: [7,6,4,3,1]

輸出: 0

解釋: 在這種情況下, 沒有交易完成, 是以最大利潤為 0。

思路1：暴力破解

代碼段1：超過執行時間

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        result = 0
        if(len(prices) == 1): return result
        for i in range(0, len(prices)-1):
            for j in range(i+1, len(prices)):
                if(prices[i] < prices[j]):
                    temp = prices[j] - prices[i]
                    result = max(result, temp)
        return result
           

總結：

1. 199/200通過，下次使用雙循環暴力破解的時候一定要慎重，leetcode一定會給你留一個用例用來跑時間複雜度

思路2：和之前做過的leetcode 53.maximum-sum-subarray最大子序和一樣，當雙層for循環時需要考慮從零開始，你是不是真的需要雙層for循環

代碼段2：執行通過

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        result = 0
        if(len(prices) == 1 or len(prices) == 0): return result
        high, low = 0, prices[0]
        for i in range(0, len(prices)):
            temp = prices[i]
            low = min(low, temp)
            high = max(high, temp - low)
        return high
           

總結：

1. 不斷地寫代碼考慮各種特殊場景，代碼非常備援。
2. 看到官方解法對于float('inf')正無窮，float('-inf')負無窮用的特别好，為代碼減壓，能使代碼優雅不少。上個代碼段和下邊我使用正無窮後的執行用時、記憶體消耗分别為    48 ms    14.7 MB |  56 ms    14.6 MB

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        high, low = 0, float('inf')
        for price in prices:
            low = min(low, price)
            high = max(high, price - low)
        return high
           

後續優化：

動态規劃