題目網址：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/

題意：給一 array prices, 從左到右分別是每天的股票價格, 求如何買賣可以獲得最大的利潤。

注意：買入的天數必須在賣出的天數之前。

Solution：

想法：利用 Greedy, 紀錄前 i - 1 天的最大利潤、最小價格, 然後計算第 i 天的利潤並比較

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res = 0; // 紀錄前 (i - 1) 天的最大利潤
        int minPrice = prices[0];// 紀錄前 (i - 1) 天的最小價格

        for (int i = 1; i < prices.size(); ++i) {
            res = max(res, prices[i] - minPrice);
            minPrice = min(minPrice, prices[i]);
        }

        return res;
    }
};
  • time：$O(n)$ ➔ 遍歷 prices
  • space：$O(1)$ ➔ 只需要常數空間