一、題目介紹

本題為LeetCode的Best Time to Buy and Sell Stock。
給定一個整數陣列prices，其中prices[i]代表第i天的股票價格。

只能選擇：
一天買入股票，在之後的某一天賣出股票，目標是找出能獲得的最大利潤。
如果無法獲得正利潤，則回傳0。

ex：prices = [7, 1, 5, 3, 6, 4]
最佳選擇：在第二天時買入1，第五天時賣出6，最大利潤=6-1=5
因此輸出為5

二、解題思路

最直覺的方法，是把每一天當作買入日，再尋找後面價格最高的賣出日。
但這樣需要比較很多組合，時間複雜度會達到O(n²)。
因此本題可以使用一次陣列走訪來解決。

我們在走訪陣列時維護兩個資訊：

1. minPrice：目前看過的最低價格
2. maxProfit：目前可以得到的最大利潤

當遇到新的價格price時：
如果price比minPrice小 → 更新最低買入價格
否則 → 計算今天賣出的利潤 → 更新最大利潤

利潤計算方式：profit = price - minPrice
ex：prices = [7, 1, 5, 3, 6, 4]

最後得到：maxProfit = 5

三、解題流程

可以將演算法整理成以下步驟：

1. 將第一個價格設定為目前最低價格。
2. 將最大利潤初始化為0。
3. 依序走訪prices。
4. 如果目前價格低於minPrice，更新minPrice。
5. 否則計算目前價格賣出時可以得到的利潤。
6. 更新maxProfit。
7. 所有價格走訪完成後，回傳maxProfit。

這樣只需要走訪陣列一次，就能找到最佳答案。

四、Java實作

五、Python實作

六、時間與空間複雜度

Java

• Time：O(n)
  • 只需要將陣列走訪一次。
  • 每個元素只處理一次。
• Space：O(1)
  • 只使用minPrice、maxProfit、profit等固定數量的變數。
  • 不需要額外建立與陣列大小相關的資料結構。

Python

• Time：O(n)
  • 使用一次for迴圈走訪所有價格。
• Space：O(1)
  • 只使用固定數量的變數。
  • 沒有建立額外的List或其他與n成正比的資料結構。

七、Java與Python解法比較

1. 陣列的表示方式

   • Java：int[] prices
     表示整數陣列，陣列的元素型別需要明確指定為int。
   • Python：prices
     Python的List不需要事先宣告元素型別，因此使用上更加簡潔。

2. 陣列走訪方式

   • Java：for (int price : prices)
   • Python：for price in prices:
     兩種語言都可以直接取得陣列中的每個元素，因此不需要使用索引進行計算。

3. 最大值的處理方式

   • Java：Math.max(maxProfit, profit)
   • Python：max(max_profit, profit)
     功能相同，都是比較目前最大利潤與這次計算出的利潤，保留較大的值。

4. 資料結構與記憶體
   本題不需要額外建立Hash Table、Stack等資料結構，只需要使用陣列本身以及幾個變數即可。因此 Java 與 Python 的空間複雜度皆為：O(1)。

八、實作結果

LeetCode測試結果：Accepted

九、今日學習心得

今天學習了如何利用陣列走訪解決股票買賣的最大利潤問題。

一開始可能會想到將每一天的買入價格與後面的賣出價格全部進行比較，但這種方法需要大量的重複計算。透過在走訪陣列的過程中記錄「目前最低價格」，就可以在一次走訪中計算出最佳利潤。

這讓我了解到，解題時不一定需要保存所有過去的資料，而是可以思考哪些資訊才是真正需要保留的。本題只需要記錄目前最低價格與最大利潤，就能將時間複雜度從O(n²)降低到O(n)，同時維持O(1)的額外空間。

今天的重點：陣列走訪 → 記錄最低價格 → 計算目前利潤 → 更新最大利潤