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

#include <array>
#include <vector>
class Solution {
public:
    bool check(vector<int> in, vector<int> out) {
        if(in.size() != out.size()) return false;
        array<int, 2005> arr;
        for(auto x: in) {
            arr[x + 1000] = 1;
        }
        for(auto x: out) {
            if(--arr[x + 1000] != 0) return false;
        }
        return true;
    }
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        stack<int> stk;
        array<int, 2005> arr {};
        
        if(!check(pushV, popV)) return false;

        while(!popV.empty()) {
            //入栈
            while(stk.empty() || (stk.top() != popV.front() && !pushV.empty())) {
                if(arr[popV.front() + 1000]) return false;
                stk.push(pushV.front()); 
                arr[stk.top() + 1000] = 1;
                pushV.erase(pushV.cbegin());
            }
            if(stk.top() != popV.front() && arr[popV.front() + 1000]) return false;
            //出栈
            while(!stk.empty() && stk.top() == popV.front()) {
                //cout << stk.top() << " ";
                arr[stk.top() + 1000] = 0;
                stk.pop();
                popV.erase(popV.cbegin());
            }              
        }
        return true;
    }
};