一个数组上的两个极值的协调交互优化问题（C++）

一个数组上的两个极值的协调交互优化问题（C++）

买卖股票的最佳时机

问题：暴力法：双temp：官方方法：一次遍历

问题：

暴力法：

好家伙。。。不出所料，超时了

#include
class Solution {
public:
    int maxProfit(vector& prices) {
    int result=0;
    for (int i = prices.size()-1; i>0; i--){
        for (int j=i-1; j>=0; j--)
        if(prices[i]>prices[j]){
            result=max(prices[i]-prices[j],result);
        }
    }
    return result;
    }
};

双temp：

思考一下这是一个最优解的问题，修改了几轮想出了以下思路：

设定从左向右的寻找顺序设定tempMin tempMax存储当前的极值①当遇到比tempMin小的值时，此时更新tempMin，tempMax置为tempMin（因为题目的限定是极大值必然出现在极小值之后，因此之前的要清零，但清零时要注意的是之前的值也要保存）②当遇到比tempMax大的值时，更新tempMax 和result需要注意的是，如果过程①中tempMax置为INT_MIN，那么过程①②的顺序不能颠倒！！！因为这样以后，如果先进行②的判断那么必然成立！！！经过个人经验，对数组的大小类 *** 作，不如将temp都设置为初始值或者初始相邻值。

#include
#include
#include
class Solution {
public:
    int maxProfit(vector& prices) {
    int pricesNum(prices.size());
    int tempMin(prices[0]),tempMax(prices[0]);
    int result(0);

    for (int i=1; i prices[i] ){
            tempMin = prices[i];
            //tempMax = INT_MIN;//这样以后else if如果在前面则必然执行
            tempMax = tempMin;
            
        }
        else if (tempMax < prices[i]){
            tempMax = prices[i];
            result = max(tempMax-tempMin,result);
        }
    }
    return result;
    }

};

官方方法：一次遍历

抓住了核心要点，最低点买入是最好的，最低点动态变化，在变化之前拿当前利益与历史最大利益比较，和我的双temp大同小异，但是执行时间的占用内存都略逊于我的方法：
自己设置了一个inf倒是 - - 省下INT_MIN/MAX了

class Solution {
public:
    int maxProfit(vector& prices) {
        int inf = 1e9;
        int minprice = inf, maxprofit = 0;
        for (int price: prices) {
            maxprofit = max(maxprofit, price - minprice);
            minprice = min(price, minprice);
        }
        return maxprofit;
    }
};
作者：LeetCode-Solution