121. Best Time to Buy and Sell Stock

題目描述

給定一個陣列 prices，其中 prices[i] 表示某支股票在第 i 天的價格。你只能選擇在某一天買入這支股票，並在未來的某一天賣出，且買入日與賣出日必須不同。請求出你可以獲得的最大利潤。如果無法獲得任何利潤，則返回 0。

Example:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: 在第 2 天以價格 1 買入，在第 5 天以價格 6 賣出，獲利為 6 - 1 = 5。
注意，不能在第 2 天買入後於第 1 天賣出，因為必須在買入之後才能賣出。

解題思路:
這題是模擬股票買賣中如何找到最大利潤的問題。由於題目規定只能買賣一次，所以解題的關鍵在於找到最低的買入價格，並在每一天的價格中計算當前價格與最低買入價格的差值，然後不斷更新最大利潤。具體來說，我們需要遍歷價格列表，依次找到當前最小的價格，並計算出當天賣出時的潛在利潤，將這個潛在利潤與已經記錄的最大利潤相比，更新最大的值。

var maxProfit = function(prices) {
    if (prices.length === 0) return 0;

    let minPrice = prices[0];
    let maxProfit = 0;

    for (let i = 1; i < prices.length; i++) {
        if (prices[i] < minPrice) {
            minPrice = prices[i];
        } else {
            maxProfit = Math.max(maxProfit, prices[i] - minPrice);
        }
    }

    return maxProfit;
};

時間複雜度為 O(n)，因為我們只需要遍歷一次 prices 陣列來找出最大利潤。
空間複雜度為 O(1)，因為只需要使用常數空間來儲存 minPrice 和 maxProfit 這兩個變數，不會額外佔用其他空間。

總結:
這道題目可以歸類為「for 迴圈」。在 LeetCode 上，與股票買賣相關的題目總共有四題，根據不同的買賣條件，難度和解法也會有所不同。這題只允許進行一次買賣，所以難度屬於 Easy 等級。而下一題允許多次買賣，難度就提升到 Medium 等級。不論如何，讀者可以試著畫出股價的變化圖，觀察如何找到最大利潤，這樣自然就能想出用程式解決的方式。

這些股票題目不僅鍛鍊我們的邏輯思維，還讓我們學會如何有效利用變量來記錄和更新數據，進而找到最優解。對於入門來說，建議從最簡單的情況開始練習，逐步加深對問題的理解。