[LeetCode] Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

分析一：使用兩個輔助數組min_prices和max_prices。min_prices的第i個元素表示到第i天前最小的價格。max_prices的第i個元素表示第i天後最大的價格。時間複雜度O(n),空間複雜度O(n)

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.empty()) return 0;
        int prices_size = prices.size();
        vector<int> min_prices(prices_size, prices[0]);
        vector<int> max_prices(prices_size, prices[prices_size - 1]);
        
        for (int i = 1; i < prices_size; i++) {
            if (prices[i] < min_prices[i-1]) {
                min_prices[i] = prices[i];
            } else {
                min_prices[i] = min_prices[i-1];
            }
        }
        
        for (int i = prices_size - 2; i >= 0 ; i--) {
            if (prices[i] > max_prices[i+1]) {
                max_prices[i] = prices[i];
            } else {
                max_prices[i] = max_prices[i+1];
            }
        }
        
        int max_gap = 0;
        for (int i = 0; i < prices_size; i++) {
            int temp_gap = max_prices[i] - min_prices[i];
            if (temp_gap > max_gap) max_gap = temp_gap;
        }
        
        return max_gap;
    }
};      

分析二：我們完全可以不借助于這兩個數組。時間複雜度O(n),空間複雜度O(1)

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) return 0;
        
        int min_price = prices[0];
        int max_profit = 0;
        for (int i = 1; i < prices.size(); i++) {
            if (prices[i] < min_price) {
                min_price = prices[i];
            }
            
            max_profit = max(max_profit, prices[i] - min_price);
        }
        
        return max_profit;
    }
};