學習路線/貪婪演算法

121. 買賣股票的最佳時機

Easy

Best Time to Buy and Sell Stock

ArrayGreedy

題目描述

給定一個陣列 prices，其中 prices[i] 是股票第 i 天的價格。選擇某一天買入、之後某一天賣出，求能獲得的最大利潤。若無法獲利則返回 0。

LeetCode 121原題連結 →

解法思路

  1. 維護一個變數 minPrice 記錄遍歷過程中的最低買入價
  2. 對每一天計算若今天賣出的利潤 = prices[i] - minPrice
  3. 更新最大利潤 maxProfit
  4. 一次遍歷即可完成，貪婪地在最低點買入

複雜度分析

  • 時間複雜度：O(n)
  • 空間複雜度：O(1)
當前掃描
最低買入點 (min)
最佳買入
最佳賣出
7
D1
1
D2
5
D3
3
D4
6
D5
4
D6
最低買入價
∞
當前利潤
-
最大利潤
0
演算法開始：初始化最低價格 (minPrice) 為無限大，最大利潤 (maxProfit) 為 0。
1 / 16