问题抽象

判断给出的 栈弹出序列 是否为对应的 栈压入序列 的合法弹出序列

算法：模拟

经典题，用一个栈来模拟即可。正常每次压入一个元素，并按照给定的弹出序列尽量多地弹出元素

最终能把压入的所有元素按照弹出序列全部弹出的话，就说明合法

复杂度

时间：$O(N)$
空间: $O(N)$

代码

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> stk;
        int j = 0;
        for(int i = 0; i < pushed.size(); i ++){
            stk.push(pushed[i]);
            while(stk.size() && stk.top() == popped[j]){
                stk.pop();
                j ++;
            }
        }
        return j == popped.size();
    }
};