美文网首页
【剑指 offer】栈的压入弹出序列

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

作者: 邓泽军_3679 | 来源:发表于2019-04-13 10:37 被阅读0次

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();
    }
};

相关文章

网友评论

      本文标题:【剑指 offer】栈的压入弹出序列

      本文链接:https://www.haomeiwen.com/subject/pdhlwqtx.html