繼第二天的「160. Intersection of Two Linked Lists」，今天來解 121 這題！還沒看過第二天或再之前天數的朋友，歡迎也去看看~

我們開始吧！

前言

這篇會加入如何規劃、以及如何模擬解法的概略說明，別錯過囉！

基本資訊

• 難度： Easy
• 網址： https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

演算法與資料結構

• Greedy, Array

題意

給予一個 prices 陣列，而 prices[i] 的 i 為第 i 天的股價。

需要得透過選擇一天買入，並在該天的未來日賣出，需要得出最大獲利並回傳。

如果無法獲利，則回傳 0 。

範例

範例 1 - 有獲利

prices = [7, 1, 5, 3, 6, 4]

天數為 array 之 index 。以這個例子在第一天 (股價: 1) 買，在第四天 (股價: 6) 賣出能得到最大獲利

6 - 1 = 0

範例 2 - 沒有獲利

prices = [5, 4, 3]

同樣，天數為 array 之 index 。以這個例子在最便宜的第二天 (股價: 3) 買，但是在那之後已經無法交易了，所以沒有獲利，因此回傳 0 。

1. 暴力解 - 雙迴圈

規劃

提早結束條件

• 陣列為空和只有一個數值時，無法交易，直接回傳 0

接著思考核心的 routine

1. 宣告一個 maxProfit ，暫存最大的獲利
2. 以雙指標的概念，左指標為外層迴圈，右指標為內層迴圈
3. 走訪內層迴圈時，逐一確認 右指標的值 - 左指標的值 是否大於 maxProfit ，若大於則更新 maxProfit ，否則不做任何事
4. 一直走訪完所有元素結束運算
5. 回傳 maxProfit

程式碼

class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        if prices.isEmpty { return 0 }
        
        var maxProfit = 0
        
        for buy in 0..<(prices.count-1) {
            for sell in buy..<prices.count {
                maxProfit = max(maxProfit, prices[sell] - prices[buy])
            }
        }
        
        return maxProfit
    }
}

執行結果

Time Limit Exceeded

複雜度分析

2. 簡化走訪方式 - 貪婪

在解法 1 中只有暫存最大獲利，但是每一次都在重新尋找最低值。如果能夠以貪婪的方式，只要找到最低值就暫存下來，就可以避免不需要的計算。

• 價格在相對低點是好買點 → 逐步更新最低價
• 價格在相對高點是好賣點 → 逐步更新最大獲利

規劃

提早結束條件

• 陣列為空和只有一個數值時，無法交易，直接回傳 0

準備必要的變數

1. 宣告一個 minPrice 並給初始值為 Int.max
2. 宣告一個 maxProfit ，暫存最大的獲利

接著思考核心的 routine

1. 走訪陣列，在每一個元素

• 試著取得最小買入值
• 試著根據最新的最小值取得最大獲益

2. 走訪完所有元素
3. 回傳 maxProfit

驗證與討論 routine

當規劃完核心 routine 之後，可以試著用紙筆模擬走訪的結果，同時並思考有沒有邏輯錯誤和 edge cases 。

在面試的情境下，這個階段可以跟面試官討論自己的思考方式，除了可以在動手前確保邏輯沒問題，也可以從面試官的回饋得知可能缺失的地方。

確認沒有問題後，再開始動手開始寫程式碼也還來得及。

程式碼

class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        if prices.isEmpty { return 0 }

        var minPrice = Int.max
        var maxProfit = 0
        
        for price in prices {
            minPrice = min(minPrice, price)
            maxProfit = max(maxProfit, price - minPrice)
        }
        
        return maxProfit
    }
}

執行結果

• Runtime: 778 ms (Beats 47.22%)
• Memory: 18.1 MB (Beats 16.9%)

複雜度分析

解法比較

結語

從 Greedy 的角度思考的時候，會開始想如何簡化掉不必要的運算，就能夠大大降低時間複雜度，減少運行時間。但是該怎麼降，還是需要多做題目體會換經驗。

如果有任何回饋或是文中寫不清楚的地方，歡迎在下面留言！

今天就到這裡，明天見！