121. Best Time to Buy and Sell Stock

1.問題

• 股票最高獲利? (只能買賣一次)

2.想法

• 提問

  • 確認題意:

• function header, parameter

• test input

• 觀察

  • 依題意是找出最大值與最小值的差值

• 說明想法

  • 每次移動指標時, 跟最小值比較, 以得到新的最小值

  • 每次移動指標時, 將該次的值減去最小值, 並將差值與目前差值的最大值比較

• 測試計算複雜度

3.程式碼

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