【Leetcode 筆記】 121. Best Time to Buy and Sell Stock

題目解釋

給定一個 prices，其中 prices[i] 是 給定股票第 i 天的價格。 您希望透過選擇某一天購買一隻股票並選擇未來的另一天出售該股票來最大化您的利潤。 回傳您可以從本次交易中獲得的最大利潤。如果無法獲得任何利潤，則 return 0。

範例

• 輸入: prices = [7, 1, 5, 3, 6, 4]
• 輸出: 5

第 2 天買入（價格 = 1）並在第 5 天賣出（價格 = 6），最大利潤 = 6-1 = 5。

最佳解法

步驟

1. 令雙指標 left 跟 right, right 要比 left 前面一格
2. 每次都求一遍現在的 profit (curr_profit)
   • if 現在的利潤 curr_profit 比 max_profit 大，代表 left 不用動，繼續 traverse 整條 prices
   • if 現在的利潤 curr_profit 比 max_profit 小，代表現在 left 所指的值可能太大，因此直接將 left 移動到跟 right 一樣的地方
   • => 總之最後 right 都得向前移動一格
3. 開心回傳 max_profit

程式碼

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

        while (left < right) and (right <= len(prices) - 1):
            curr_profit = prices[right] - prices[left]
            if curr_profit >= 0:
                max_profit = max(curr_profit, max_profit)
            else:
                left = right
            right += 1

        return max_profit

時間複雜度

O(n)，n 是 prices 的元素個數。

空間複雜度

O(1)。

結語

可見量化交易的最大難題不是求最大 profit 而是通靈出未來的價格🔮💵

• About
• Latest Posts

數據女巫 𝔻.𝕡𝕪𝕤 🔮

𝐀𝐈 𝐀𝐫𝐭𝐢𝐬𝐭 • 𝐒𝐨𝐟𝐭𝐰𝐚𝐫𝐞 𝐄𝐧𝐠𝐢𝐧𝐞𝐞𝐫
﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊
致力於打破現有框架的 AI 藝術創作者，曾接受藝文雜誌的個人專訪，作品於香港實體展出。有擔任大學講座講師與 Stable Diffusion AI 年會講者的經驗。擅長 Live Prompting，曾獲 GIGABYTE VS AI 街頭對戰冠軍、ASUS 校園 AI 繪圖競賽亞軍等殊榮。
---
歡迎合作邀約 / 委託 / 各式交流
ᴇᴍᴀɪʟ：dpys@techmagichouse.art

Latest posts by 數據女巫 𝔻.𝕡𝕪𝕤 🔮 (see all)

• [推薦工具] 讓程式碼截圖變的美美的吧！VScode CodeSnap 與 3 種同功能線上工具介紹 - 2025-01-05
• [AI 繪圖初級教學] 用 X/Y/Z Plot 比較 Stable Diffusion 的 prompt 與 LoRA 效果 - 2024-12-27
• [AI 繪圖中級篇教學] Stable Diffusion WebUI WD14 Tagger 介紹 - 2024-12-26