【一刷《剑指Offer》】面试题 22：栈的压入、弹出系列

力扣对应题目链接：946. 验证栈序列 - 力扣（LeetCode）

牛客对应题目链接：栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com)

核心考点 ：栈的理解。

一、《剑指Offer》内容

二、分析题目

要判定第二个序列是否可能是该栈的弹出序列，就要使用指定的入栈顺序模拟出来对应的弹栈序列，我们设入栈顺序序列式 pushV，可能出栈序列  popV。

popv  的第一个元素，一定是最后入栈，最先弹栈的， 而我们的入栈顺序是一定的，也就决定了，我们必须一直入栈，直到碰到 popv  的第一个元素，然后开始弹栈。最后在循环这个过程，如果符合要求，最后栈结构一定是空的。

1. 遍历入栈序列，只要 popv 的第一个数据和当前 pushv 的数据不相等，一直进行入栈操作。
2. 只要 st 栈顶值和 popv 的出栈序列数据是相等的，则一直执行出战逻辑
3. 返回 st.empty()

三、代码

//牛客
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pushV int整型vector 
     * @param popV int整型vector 
     * @return bool布尔型
     */
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        if(pushV.empty() || popV.empty() || pushV.size()!=popV.size())
            return false;
        stack<int> st;
        int j=0;
        for(int i=0; i<pushV.size(); i++)
        {
            st.push(pushV[i]);
            while(!st.empty() && st.top()==popV[j])
            {
                st.pop();
                j++;
            }
        }
        if(st.empty()) return true;
        else return false;
    }
};

//力扣
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        if(pushed.empty() || popped.empty() || pushed.size()!=popped.size())
            return false;
        stack<int> st;
        int j=0;
        for(int i=0; i<pushed.size(); i++)
        {
            st.push(pushed[i]);
            while(!st.empty() && st.top()==popped[j])
            {
                st.pop();
                j++;
            }
        }
        return st.empty();
    }
};