【剑指 offer】栈的压入弹出序列

1、题目描述

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

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

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

2、问题描述：

• 第一个序列是一个压入栈的顺序，判断，第二个序列是否可能是第一个的弹出序列。

3、问题关键：

• 栈可以一边压入，一遍弹出。
• 如果一个数在最上面，如果它不立刻弹出，它不能比它后面的先弹出。
• 做法是，依次将第一个序列压入栈中。对于第二个序列，第一个序列第一个元素一定是第一个弹出的。所以判断栈顶元素，是否和第一个元素相同，相同就弹出，第二个也向后移动一位。结束时判断栈为空则返回true。

4、C++代码：

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