题解 | #栈的压入、弹出序列#

虽然题目没说输入用例都是从小到大输入，但是使popV中出现pushV中没有的值实在是...

class Solution {
public:
    //map<int,int> Index;//值映射索引
    map<int,bool> Exist;

    bool IsPopOrder(vector<int> pushV,vector<int> popV) {

        int len = pushV.size();//

        //以第一个出栈4为分界线 
        //已入栈的123遵循   xx3xx2xx1xx
        //为入栈的5,6,7      ..xx5xx6xx7xx\xx6xx7xx5xx\xx5xx7xx6xx\xx6xx5xx7xx\xx7xx6xx5xx
        //无xx7xx5xx6xx

        for(int i=0;i<len;i++) 
            //Index[pushV[i]] = i;//防非由小到大顺序输入,但是可以不用，因为用例不存在非→输入
            Exist[pushV[i]] = true;

        for(int v:popV) if(!Exist[v]) return false;//有一个输入用例里面popV中含有pushV未输入的值

        int min_=INT_MIN,max_=INT_MIN;

        for(int i=0;i<len;i++)
        {
            while(popV[i]<max_) //比如检测通过了4，然后直接跳到5去，避免popV[i]=在4之前的3,2,1
            {
                i++;
                if(i>=len-1) break;
            }

            //只有满足大于max(当前popV[i]),max需要记录
            //或者小于min_(变化，表示→由max-1到1的递减变化.出现大于min说明是非递减)
            max_ = popV[i];
            min_ = popV[i];

            for(int j=i+1;j<len;j++)
            {
                if(popV[j]<popV[i]&&popV[j]>min_) return false;//比如 43512 中 2比1大，但是小于4,说明不满足321栈倒出顺序
                //              4           1  第一次
                min_ = min(min_, popV[j]);
            }
        }

        return true;

    }
};