题目

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。

假设压入栈的所有数字均不相等。

例如序列 1,2,3,4,5 是某栈的压入顺序，序列 4,5,3,2,1是该压栈序列对应的一个弹出序列，但 4,3,5,1,2就不可能是该压栈序列的弹出序列。

注意：若两个序列长度不等则视为并不是一个栈的压入、弹出序列。若两个序列都为空，则视为是一个栈的压入、弹出序列。

样例

输入：[1,2,3,4,5]
      [4,5,3,2,1]

输出：true

思路
(模拟 )$O(n)$

{:width=”75%”}

我们定义一个空栈st，然后模拟这个过程。

假设我们已经处理了出栈序列中的前i-1个数，现在要让popV[i]出栈。如果popV[i]不在栈中，我们就要将入栈序列pushV[i]中的若干个数压进栈中，直到popV[i]入栈。

• 如果当前要出栈的popV[i]元素在栈首，那么我们将其弹出。
• 如果当前要出栈的popV[i]元素不在栈首，那么原问题无解。

最后判断st是否为空，为空则表示当前出栈序列可取。
时间复杂度分析

遍历整个出栈序列的时间复杂度为$O(n)$,while循环最多执行n次，因此总的时间复杂度为$O(n)$
代码

class Solution {
public:
    bool isPopOrder(vector<int> pushV,vector<int> popV) {
        if(pushV.size()!=popV.size()) return false; //两个序列长度不等，直接返回false
        stack<int>st;
        int k  = 0;
        for(int i = 0; i < popV.size(); i++)
        {
            while(st.empty()||popV[i] != st.top()) st.push(pushV[k++]);
            if(st.top() == popV[i]) st.pop();
            else return false;
        }
        return st.empty();
    }
};