題目資訊

• 題目編號: 121
• 題目連結: Best Time to Buy and Sell Stock
• 主題: Array, Dynamic Programming

題目敘述

您有一個陣列 prices，其中 prices[i] 是某支股票在第 $i$ 天的價格。

您想透過選擇某一天買入一支股票，並選擇未來的不同一天賣出該股票來最大化您的利潤。

返回您可以從這次交易中獲得的_最大利潤_。如果無法實現任何利潤，則返回 0。

範例 1:

輸入: prices = [7,1,5,3,6,4]
輸出: 5
解釋: 在第 2 天（價格 = 1）買入，在第 5 天（價格 = 6）賣出，利潤 = 6-1 = 5。
請注意，不能在第 2 天買入並在第 1 天賣出，因為必須先買入後賣出。

範例 2:

輸入: prices = [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下，未進行任何交易，因此最大利潤 = 0。

約束條件:

• $1 \leq \text{prices.length} \leq 10^5$
• $0 \leq \text{prices}[i] \leq 10^4$

直覺

該問題要求我們找出能獲得最大利潤的買賣股票的日子，其中必須先買後賣。問題的挑戰在於如何在限定條件下（即股票必須在售出之前購買）最大化售價與買價之間的差值。換言之，我們要找到 (buy, sell) 這對日子組合，使得 sell > buy 且利潤 (prices[sell] - prices[buy]) 最大化。

解法

為了解決這個問題，該方法的核心在於遍歷 prices 陣列時維持兩個資訊：目前所看到的最低價格和在每一步所能達到的最大利潤。演算法的步驟概述如下：

1. 初始化變數 max_profit 為 0，用以存儲可達到的最大利潤。
2. 將 min_price 初始化為 prices 陣列的第一個元素，代表迄今為止遇到的最低買入價格。
3. 從第二個元素開始遍歷 prices 陣列。對於每一個價格：
   • 計算如果在當天賣出股票的潛在利潤。這可以通過用當天的價格減去目前的 min_price 得出。
   • 更新 max_profit 為其目前值和計算出的潛在利潤中的較大者。
   • 更新 min_price 為其目前值和當天價格中的較小者，以反映迄今為止遇到的最低買入價格。
4. 完成整個陣列的遍歷後，max_profit 會包含依照問題規則可達到的最大利潤。
5. 返回 max_profit 作為結果。

此方法在遍歷陣列時有效地計算出結果，時間複雜度為 $O(n)$，其中 $n$ 是 prices 陣列的長度。空間複雜度為 $O(1)$，因為只使用了固定數量的額外變數。

程式碼

C++

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int max_profit = 0;  // 將最大利潤初始化為0。
        int min_price = prices[0];  // 將最低價格初始化為第一天的價格。
        
        // 從第二天開始遍歷價格。
        for (int i = 1; i < prices.size(); ++i) {
            // 計算在第i天賣出的潛在利潤。
            max_profit = max(max_profit, prices[i] - min_price);
            
            // 如果當前價格更低，則更新最低價格。
            min_price = min(min_price, prices[i]);
        }
        
        // 返回獲得的最大利潤。
        return max_profit;
    }
};

Python

class Solution:
    def maxProfit(self, prices):
        max_profit = 0  # 將最大利潤初始化為0。
        min_price = prices[0]  # 將最小價格初始化為第一天的價格。
        
        # 從第二天開始遍歷價格。
        for i in range(1, len(prices)):
            # 計算在第i天賣出時的潛在利潤。
            max_profit = max(max_profit, prices[i] - min_price)
            
            # 如果當前價格較低，則更新最小價格。
            min_price = min(min_price, prices[i])
        
        # 返回獲得的最大利潤。
        return max_profit

複雜度分析

• 時間複雜度: $O(n)$
  該演算法對 prices 陣列進行一次遍歷，該陣列包含 $n$ 個元素。在每次迭代中，它執行一個固定數量的工作，包括基本算術運算和比較運算。因此，時間複雜度相對於輸入陣列的大小是線性的，即 $O(n)$。

• 空間複雜度: $O(1)$
  該演算法使用固定數量的額外空間，無論輸入大小如何。它使用了一些整數變量（max_profit 和 min_price），這些變量不依賴於輸入陣列的大小。因此，空間複雜度是恆定的，即 $O(1)$。