剑指Offer第21题：栈的压入、弹出序列

发表于 更新于 分类于

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

解题思路：定义一个辅助栈，对按照pushV的顺序进栈，直至栈顶元素和popV中的第0个元素相等，之后弹出该元素，并将popV的指针右移一位，再判断此时辅助栈的元素和popV中的下一个元素是否相等，循环直至辅助栈为空，或者元素不相等为止。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
bool IsPopOrder(vector<int> pushV,vector<int> popV) {
    vector<int> tmp;
    int i = 0;
    for (auto v:pushV) {
        tmp.push_back(v);
        while (i < popV.size() && tmp.back() == popV[i]) { //注意：要限定i的范围
            tmp.pop_back();
            i += 1;
        }
    }
    return tmp.empty();
}