題目出處
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 邊際情況處理
初始值處理
- 第一天時，因為沒有最大值，我特別去判斷現在進來的是不是第一天，
這個可以成功的原因是因為：
題目限制「0 <= prices[i] <= 10^4」
兩種作法應該都可以，我之後應該會選擇第一種，去避免自訂義值的情況。