Offer 31. 栈的压入、弹出序列

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

辅助栈

思路

通过一个辅助栈来判断压栈所对应的出栈序列是否可行。

算法

• 按压栈顺序将元素压入辅助栈
• 判断当前栈顶是否与出栈序列当前值相同，若相同弹出，并继续比较

• 返回值判断辅助栈是否为空

  实现

  bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
    stack<int> tmp;
    for(int i=0,cnt=0;i<pushed.size();i++){
        tmp.push(pushed[i]);
        while(!tmp.empty() && tmp.top()==popped[cnt]){
            tmp.pop();
            cnt++;
        }
    }
    return tmp.empty();
  }

  复杂度分析

• 时间复杂度:

• 空间复杂度:

算法2

思路

算法

实现

复杂度分析

• 时间复杂度:
• 空间复杂度:

题目标题难度划分

算法掌握难度程度划分