【LeetCode】Best Time to Buy and Sell Stock – 殺進殺出 – 數列、雙指標

tags: leetcode

題目 Leetcode 121

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/

思路

1. 先看清楚題目，Stock的意思是股票，你要在股價走勢圖中找到能獲利最多的進場 (Buy) 和出場的時間點 (Sell)
2. 所以是找兩數之差為最大，這樣豈不是 max(prices) - min(prices) 就結束了嗎? 錯！錯！錯
3. 有一個條件是這題的核心精神: 賣的那天不能早於買的那天
4. 有點難…那就窮舉！！！ 寫起來跟 two-sum 很像 (解法一)
5. 然後就Timeout了…
6. 這題在算 max profit 時永遠只有兩個數字在相減，又不能窮舉的話，可以想到雙指標 (或是 sliding window)
7. 我們用 l (left pointer) 代表買的那天， r (right pointer) 代表賣的那天，那profit就會是 prices[r] - prices[l]
8. 超級重要的精神: 把 l 站穩，讓 r 去探索 (如圖) ，直覺上來看，當我們找到一個低點 (把 l 站穩)，那就繼續往後去找高點 (讓 r 去探索)，而且越高越好！

9. 有什麼限制條件呢?
   • r >= l
   • r <= len(prices)
10. 有什麼資訊要紀錄下來呢?
    • max profit (一拿到最大的獲利就馬上更新)
    • min value (看到新的低點，就讓 l 站過去)
11. l 和 r 如何更新呢?
    • r +=1 (讓 r 去探索)
    • if prices[r] < min_value: l = r (當 r 探索新的低點，就讓 l 站過去)
12. 此時我們寫下解法二

解法一

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # Solution 1: Time Out
        n = len(prices)
        result = 0
        for i in range(n-1):
            buy_price = prices[i]
            for j in range(i, n):
                sell_price = prices[j]
                profit = sell_price - buy_price
                if profit > result:
                    result = profit
        return result 

解法二

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # Solution 2: 
        n = len(prices)
        if n == 1: 
            return 0

        l = 0
        r = 1
        min_val = 99999
        max_profit = 0
        while r!= n:
            if prices[r] - prices[l] > max_profit:
                max_profit = prices[r] - prices[l]

            if prices[l] < min_val:
                min_val = prices[l]

            if prices[r] < min_val:
                min_val = prices[r]
                l = r
            r += 1
        return max_profit

筆記

• 這邊的影片講解的非常好，用到雙指針：https://www.youtube.com/watch?v=1pkOgXD63yU&ab_channel=NeetCode
• 這題蠻多人在抱怨說不是 Easy，應該屬於 Medium 的難度，所以第一次沒做出來不要灰心…
• 這題在寫的時候可能會覺得怪怪的，雙指標這樣搞真的能找到最大獲利嗎？其實這個演算法是有點違反因果律的…因為你可以回到過去改變你買進的那天…再想一下或許就不會覺得那麼怪了
• HackMD 筆記: https://hackmd.io/@ga642381/HJ2D5PGts