LeetCode 筆記 - 121. Best Time to Buy and Sell Stock

LeetCode 基礎經典題,探討股票買賣的最大獲利。解題邏輯聚焦於尋找歷史最低點,並在遍歷過程中不斷計算目前價格與低點的差額,進而找出最高獲利。本文分享如何用簡單的一次遍歷 O(N) 達成最佳化解法。

發佈
閱讀
約 1 分鐘
字數
225
⚠️ 舊文提醒:本文發佈於約 4 年前,部分內容或指令可能已過時,請斟酌參考。

題目在此 121. Best Time to Buy and Sell Stock

給定每天股票的價格,請找出一買一賣之間,最大的獲利是多少

解題思維

基本邏輯很簡單

  1. 如果找到新低點,那清空之前的最高價,因為你不可能今天買了回到過去賣
  2. 如果找到新高點,那請根據目前的低點計算獲利,並記錄最高的獲利

完成 😆

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def maxProfit(self, prices: List[int]) -> int:

low_price = prices[0]
high_price = 0

result = 0
for p in prices:

if low_price > p:
low_price = p
high_price = p + result
elif high_price < p:
high_price = p

result = max(result, high_price - low_price)

return result

也許你也會想看看

輸入關鍵字開始搜尋 · ↑↓ 選擇 · Enter 開啟