美文网首页
122. Best Time to Buy and Sell S

122. Best Time to Buy and Sell S

作者: 刘小小gogo | 来源:发表于2018-09-07 00:12 被阅读0次
    image.png

    只需要找连续的波谷和波峰, 在波谷买入,在波峰卖出。所以只需要判断连续的波峰和波谷就行。

    可以得到证明,最低的波谷和波峰的差值,没有其中的两个波峰波谷的差值和大,画图一看就知道了。

    更聪明的做法,将数组看成是时间序列,将后一个与前一个做差,只需要加起来所有的正值即可。

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

    相关文章

      网友评论

          本文标题:122. Best Time to Buy and Sell S

          本文链接:https://www.haomeiwen.com/subject/kpqqgftx.html