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

审题后从输入序列和输出序列入手，发现规律：当两个元素在输入序列中的先后顺序与在输出序列中一致时，在这两个数之后输入的数必不可能在这两个数之前输出。
围绕这一发现，设计算法逻辑：
用一个辅助数组seq来储存输入序列的元素在输出序列中的位置，如seq[0]则表示输入序列中第一个元素在输出序列中的位置。
遍历seq，seq中某两个元素的值的大小关系与其序号的大小关系一致时，则这两个元素输入输出的先后顺序一致，进而判断seq中在这两个元素之后的元素。
若之后的元素中有比这两个元素的值小的，则可知有在其后输入的元素在其前输出了，返回false。否则继续，直至遍历seq中所有数对。

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        vector<int> seq;
        for(int i = 0;i < pushV.size();i++){
            for(int j = 0;j < popV.size();j++){
                if(pushV.at(i) == popV.at(j)){
                    seq.push_back(j);
                }
            }
        }
        if(seq.size() < pushV.size()){
            return false;
        }
        for(int i = 0;i < seq.size()-1;i++){
            for(int j = i + 1;j < seq.size();j++){
                if(seq.at(i) < seq.at(j)){
                    for(int k = j + 1;k < seq.size();k++){
                        if(seq.at(k) < seq.at(i)){
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
};

在上述代码测试通过后，抱着虚心学习的态度，去看了其他同学使用的方法。发现模拟出入栈操作的方法更为普遍，逻辑上也更容易理解，代码也更为简洁。
一开始没有想到模拟操作的方法确实是我的经验不足。下面附上之后自己写的模拟入栈出栈操作的方法。

ps:从跑出来的时间来看，还是上面的方法更佳。

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        stack<int> stk;
        int ip = 0;
        for(int i = 0;i < pushV.size();i++){
            stk.push(pushV.at(i));
            while(!stk.empty()){
                if(stk.top() == popV.at(ip)){
                    stk.pop();
                    ip++;
                }
                else{
                    break;
                }
            }
        }
        if(stk.empty()){
            return true;
        }
        else{
            return false;
        }
    }
};