剑指offer-栈的压入弹出序列

本文为剑指 offer 系列第二十三篇。
主要知识点依旧是栈Stack，判断一个序列是否可以成为某个入栈序列的出栈序列，题目很好很经典，值得学习。

题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

解题思路

因为需要判断的出栈顺序已经确定了，所以我们只要按照压栈顺序来判断一下如此压栈能不能产生对应的出栈顺序即可。
考虑到可能中间出栈的情况，所以我们在每压入一个元素之后要进行相应的判断，如果栈顶元素和出栈数组中标记的元素是对应的，那么当前元素出栈，待判断的元素后移一位，如果不对应，则继续压栈。
直到所有元素压栈完成，可能的出栈操作结束。
这个时候看栈内是否还剩元素，如果不剩元素，那么就是依据出栈数组中的数据已经完成出栈，则出栈顺序成立。否则就是不成立。

解题代码

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        stack<int> mstack;
        int j = 0;
        for(int i = 0;i<pushV.size();i++){
            mstack.push(pushV[i]);
            while(!mstack.empty() && mstack.top() == popV[j]){
                mstack.pop();
                j++;
            }
        }
        return mstack.empty();
    }
};

时间复杂度为O(n),空间复杂度为O(n)

以上，本题结束！