LeetCode 筆記 - 121. Best Time to Buy and Sell Stock
LeetCode 基礎經典題,探討股票買賣的最大獲利。解題邏輯聚焦於尋找歷史最低點,並在遍歷過程中不斷計算目前價格與低點的差額,進而找出最高獲利。本文分享如何用簡單的一次遍歷 O(N) 達成最佳化解法。
⚠️ 舊文提醒:本文發佈於約 4 年前,部分內容或指令可能已過時,請斟酌參考。
題目在此 121. Best Time to Buy and Sell Stock
給定每天股票的價格,請找出一買一賣之間,最大的獲利是多少
解題思維
基本邏輯很簡單
- 如果找到新低點,那清空之前的最高價,因為你不可能今天買了回到過去賣
- 如果找到新高點,那請根據目前的低點計算獲利,並記錄最高的獲利
完成 😆
程式碼
1 | class Solution: |