題目出處
121. Best Time to Buy and Sell Stock
難度
Easy
題目分類
array, dynamic-programming
個人範例程式碼 – 2022/4/15
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices or len(prices) < 2:
return 0
min_buy = prices[0]
best_profit = 0
for i, today_price in enumerate(prices):
if i == 0: # pass first day
continue
else:
min_buy = min(min_buy, today_price)
best_profit = max(best_profit, today_price - min_buy)
return best_profit
算法說明
最近在練習程式碼本身就可以自解釋的 Coding style,可以嘗試直接閱讀程式碼理解
input handling
處理沒有 input 或 input 只有一天 (沒得賣啊!) 的情況,return 0
Boundary conditions
for 迴圈,不怕出界
個人範例程式碼 – 2022/3/2
class Solution:
def maxProfit(self, prices: List[int]) -> int:
min_buyin_record = 999999 # min buy in
res_record = 0 # max result
for today in range(len(prices)):
if today == 0: # first
min_buyin_record = prices[today]
else:
min_buyin_record = min(min_buyin_record, prices[today])
res_record = max(res_record, prices[today] - min_buyin_record)
return res_record
Time Complexity
O(n)
算法說明
唯一要記錄只有兩個
- 到今日之前的「購入最低價」
- 到今日之前的「最佳結果」
corner case 特殊情況處理
當只有一天時,需要回傳 0,
這邊我在初始化時解掉了。
Boundary conditions/ Edge conditions 邊際情況處理
初始值處理
- 第一天時,因為沒有最大值,我特別去判斷現在進來的是不是第一天,
不過後來有使用另外一個做法,先定義最小值為「999999」,
預設第一天就會被取代。
這個可以成功的原因是因為:
題目限制「0 <= prices[i] <= 10^4」
兩種作法應該都可以,我之後應該會選擇第一種,去避免自訂義值的情況。
Reference
⭐ Leetcode 解題紀錄 ⭐ | 題型 | 資料結構 | Python Solution | C++ Solution | Note | |
---|---|---|---|---|---|---|
⭐BFS 相關題型 ⭐ | ||||||
104 | Maximum Depth of Binary Tree | BFS (分層) | Python | |||
94 | Binary Tree Inorder Traversal | BFS (分層) | Tree | Python | 內含 處理 Tree 樹問題的重點 | |
102 | Binary Tree Level Order Traversal | BFS (分層) | Tree | Python | ||
103 | Binary Tree Zigzag Level Order Traversal | BFS (分層) | Tree | Python | ||
107 | Binary Tree Level Order Traversal II | BFS (分層) | Tree | Python | ||
133 | Clone Graph | BFS (分層) | Graph | Python | Graph 的基本操作 #重要題型 | |
127 | Word Ladder | BFS (分層), DFS | Graph | Python | ||
[Lint] 127 | Topological Sorting | BFS (拓撲) |