# 121. Best Time to Buy and Sell Stock

## 1.問題 

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

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LNP1_kABtmGKQv1SuOm%2F-LNOzgty5LVlTF9ZFo0o%2F2018092701.jpg?alt=media\&token=85411cda-47e7-40e5-8039-f98431d2acb5)

## 2.想法 <a href="#id-2-xiang-fa" id="id-2-xiang-fa"></a>

* 提問
  * 確認題意: &#x20;
* function header, parameter
* test input
* 觀察
  * 依題意是找出最大值與最小值的差值
* 說明想法
  * 每次移動指標時, 跟最小值比較, 以得到新的最小值
  * 每次移動指標時, 將該次的值減去最小值, 並將差值與目前差值的最大值比較
* 測試計算複雜度

## **3.程式碼** <a href="#id-3-cheng-shi" id="id-3-cheng-shi"></a>

```
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;
    }
};
```