121. Best Time to Buy and Sell Stock

──────────────────────────────────────────────────────────────────────

121. Best Time to Buy and Sell Stock

這個題目算是面試的高頻題目，因為一個題目可以不斷的延伸，而且根據不同的條件，在延伸的過程中不需要更改太多的答案。所以這個題目的解法雖然簡單，但是熟悉各個解題的方法更是重要。

這個題目是給定一個歷史股價，且如果只能進行一次買賣，最大的獲利為何？

思路

既然是要找最大獲利，即是股價的最低點與最高點之間的差，剛開始在寫刷題時，我就很天真的想那就找到歷史股價中的最大值與最小值，最大獲利就是兩個一相減就好，這就落入了一個很簡單的小陷阱，那就是股票的獲利一定是要先有參與市場，也就是先有了買入的動作，才會有賣出的動作（咦？我不能賣空嗎？😂）

也就是說最大獲利，不只是找到最低點的股價與最高點的股價，當買在了底點，還一定要賣得掉，當股價不斷的下跌，最大了獲利反而是不參與，整體獲利為零。

有了這個條件，其實這個題目變成了有暴力解的解法，那就是我在每個股價點，都去往回找，找出以前最小的股價點就好。

解題方向

暴力解

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit = 0

        for i in range(len(prices)):
            for j in range(i):
                if prices[i] > prices[j]:
                    max_profit = max(max_profit, prices[i] - prices[j])

        return max_profit

預先算出歷史最低價

以上這樣的方法邏輯上沒有錯，但是當刷題刷久了，就會有一個感知是這個題目應該存在優化的地方，畢竟這個解法的時間複雜度是 $O(n^2)$。並且在 Leetcode 中會遇到 TLE 。

需要優化的地方很明顯，那就是每次檢查過去歷史股價低點是一件沒有意義的事情，股價的最低點出現在某個位置後，剩餘的震盪其實都是沒有必要的，因此在尋找的過程中，應該要記錄起來，又或是說其實可以先計算出歷史的股價低點紀錄：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        historical_low_price = []
        historical_low_price.append(prices[0])
        for i in range(1, len(prices)):
            historical_low_price.append(min(historical_low_price[i - 1], prices[i]))
        

        max_profit = 0
        for i in range(len(prices)):
            if prices[i] > historical_low_price[i]:
                max_profit = max(max_profit, prices[i] - historical_low_price[i])

        return max_profit

只用一個變數追蹤最低價

如此一來，時間複雜度可以降低到 $O(n)$，但是空間複雜度也變成了 $O(n)$。

面試時，就有可能會被繼續問到，空間複雜度能不能降低呢？為什麼說空間複雜度可以被降低？以這個歷史股價為例子：

[1, 2, 3, 4, 5, 6, 7]

其歷史股價低點的紀錄就會變成：

[1, 1, 1, 1, 1, 1, 1]

似乎並不需要真的記錄所有的低點，真正重要的就是當股價到 i 天時，前面的最低點的價格就好。

題目已知的時間軸中，一開始的的價格就會是一開始的低點價格，而且這個價格其實是不可能可有任何獲利的，因為沒有買進，就不會有賣出，得知了這個標準，就可以開始檢查各個歷史股價，找出最大值了。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:

        min_cost = prices[0]

        max_profit = 0
        for i in range(1, len(prices)):
            if prices[i] > min_cost:
                max_profit = max(max_profit, prices[i] - min_cost)
            min_cost = min(min_cost, prices[i])

        return max_profit

狀態機（k = 1）

如同本文開頭所說，這個題目的做法很多且延伸也很多，當上面的做法都知道後，就可以展開其他的想法。

雖然說這個題目一定是刷題會刷到的題目，但是如果刷題刷多了，這個題目其實很像是給定一個陣列，透過不同的選擇，找出題目的最佳解，這個題目其實很符合動態規劃題目的模式，這個題目其實存在著很多比較直覺的解法，動態規劃其實是滿難想的。

這個狀態機是整個家族共用的，六題都是它的參數變化 —— 完整的推導、轉移式、以及六題的對照表整理在股票買賣家族模板。這裡先看它套在 k = 1 時長什麼樣：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:

        @cache
        def dfs(i, hold, remaining):
            if remaining == 0:
                return 0
            if i == len(prices):
                return 0

            do_nothing = dfs(i + 1, hold, remaining)

            do_something = 0

            if hold:
                do_something = prices[i] + dfs(i + 1, False, remaining - 1)
            else:
                do_something = -prices[i] + dfs(i + 1, True, remaining)

            return max(do_nothing, do_something)

        return dfs(0, False, 1)

補充

整個家族一起看：六題是同一個狀態機的六組參數，共用的推導和對照表在 股票買賣家族模板。

• 122. Best Time to Buy and Sell Stock II —— 次數無限
• 123. Best Time to Buy and Sell Stock III —— 最多兩次
• 188. Best Time to Buy and Sell Stock IV —— 最多 k 次（通解）
• 309. Best Time to Buy and Sell Stock with Cool down —— 加冷凍期
• 714. Best Time to Buy and Sell Stock with Transaction Fee —— 加手續費

複雜度

暴力解（兩層迴圈）

• 時間 $O(n^2)$ — 每一天都往回掃一遍
• 空間 $O(1)$

預先算出歷史最低價

• 時間 $O(n)$ — 兩趟線性掃描
• 空間 $O(n)$ — 存下每一天的歷史最低價

單一變數追蹤最低價

• 時間 $O(n)$ — 一趟
• 空間 $O(1)$ — 只有 min_cost 和 max_profit

狀態機（k = 1）

• 時間 $O(n)$ — 狀態數是 n × 2
• 空間 $O(n)$ — cache 加遞迴堆疊

其中 n 是天數。這題的最佳解是第三種 —— $O(n)$ 時間、$O(1)$ 空間，而且推導過程（暴力 → 前綴最低價 → 滾動變數）本身就是很好的面試敘事。