题目描述

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

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

例如序列 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)$

模拟将输入序列压入栈中，输出序列是否合法

特判：如果两个序列长度不等，则输出序列肯定是不合法的

1. 遍历输入序列，每次遍历一个数就将其压入栈中
2. 用指针 i 指向输出序列，匹配时指针后移，如果栈顶元素和输出序列 popV[i] 相等，此时必须将栈顶弹出，i 进入下一个位置继续进行匹配

   因为输入序列中每个数都不相等，所以如果此时不弹栈，之后就没机会弹出了，同时 popV[i] 就会停留在第一个数上 popV[0]，无法继续进行匹配

时间复杂度

C++ 代码

class Solution {
public:
    bool isPopOrder(vector<int> pushV,vector<int> popV) {
        if (pushV.size() != popV.size()) return false;

        stack<int> s;
        int i = 0;
        for (auto x : pushV)
        {
            s.push(x);
            while (s.size() && s.top() == popV[i]) s.pop(), i ++ ;
        }

        return s.empty();
    }
};