題目
#

leetcode 121 - Best Time to Buy and Sell Stock (題目說明請點連結)

題目簡述
#

找出買入和賣出股票的最佳時機，使得利潤最大化。

範例
#

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: 在第2天買入（價格 = 1），在第5天賣出（價格 = 6），利潤 = 6-1 = 5。
注意：不能在買入前賣出股票。

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: 在這種情況下，沒有交易完成，所以最大利潤為 0。

Example 3:

Input: prices = [3,2,6,5,0,3]
Output: 4
Explanation: 在第2天買入（價格 = 2），在第3天賣出（價格 = 6），利潤 = 6-2 = 4。

解題思路
#

這題要求我們找出買入和賣出股票的最佳時機，使得利潤最大化。我們需要找到價格陣列中的最小值和最大值，但必須在最小值之後出現最大值。

解法
#

貪心法（Greedy Approach）

維護一個變數 buy 記錄當前遇到的最低買入價格
維護一個變數 profit 記錄當前最大利潤
遍歷價格陣列，更新最低買入價格和最大利潤

步驟
#

初始化 buy = prices[0]（假設第一天買入）和 profit = 0
從第二天開始遍歷價格陣列：
- 如果當前價格比 buy 低，更新 buy 為當前價格
- 計算當前價格與 buy 的差值，更新 profit 為最大值
最終返回 profit

核心邏輯
#

buy = min(buy, current_price)
profit = max(profit, current_price - buy)

例子說明
#

prices = [7,1,5,3,6,4]

天數	當前價格	buy	操作	profit	說明
初始化	-	7	-	0	設定初始買入價格和利潤
第2天	1	1	更新buy	0	buy > 1，更新為1；profit = max(0, 1-1) = 0
第3天	5	1	不變	4	buy = 1（不變）；profit = max(0, 5-1) = 4
第4天	3	1	不變	4	buy = 1（不變）；profit = max(4, 3-1) = 4
第5天	6	1	不變	5	buy = 1（不變）；profit = max(4, 6-1) = 5
第6天	4	1	不變	5	buy = 1（不變）；profit = max(5, 4-1) = 5
最終結果	-	1	-	5	最大利潤為5

完整程式碼
#

java

class Solution {
    public int maxProfit(int[] prices) {
        // 初始化買入價格為第一天的價格
        int buy = prices[0];
        // 初始化最大利潤為0
        int profit = 0;

        // 從第二天開始遍歷價格陣列
        for(int i = 1; i < prices.length; i++){
            // 如果當前價格比買入價格低，更新買入價格
            if(buy > prices[i]){
                buy = prices[i];
            }

            // 計算當前價格與買入價格的差值，更新最大利潤
            profit = Math.max(profit, prices[i] - buy);
        }

        // 返回最大利潤 
        return profit;
    }
}