【每日一题】JZ21 栈的压入、弹出序列

当你的才华还撑不起你的野心时，你应该静下心去学习 。 题目描述

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

输入：[1,2,3,4,5],[4,3,5,1,2]
返回值：false

解题思路

1. 初始化： 辅助栈 stack ，弹出序列的索引 i；
2. 遍历压栈序列： 各元素记为 num ；
   1. 元素 num 入栈；
   2. 循环出栈：若 stack 的栈顶元素 == 弹出序列元素 popped[i]，则执行出栈与 i++ ；
3. 返回值： 若 stack 为空，则此弹出序列合法。

时间复杂度 O(N) ： 其中 N 为列表 pushed 的长度；每个元素最多入栈与出栈一次，即最多共 2N 次出入栈操作。 空间复杂度 O(N) ： 辅助栈 stack 最多同时存储 NN 个元素。

参考代码 Java版本

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack stack = new Stack();
        int i = 0;
        for(int num : pushed) {
            stack.push(num); // num 入栈
            while(!stack.isEmpty() && stack.peek() == popped[i]) { // 循环判断与出栈
                stack.pop();
                i++;
            }
        }
        return stack.isEmpty();
    }
}
// 关注TechGuide，大厂笔经面经闪电速递！

CPP版本

class Solution {
public:
    bool isPopOrder(vector pushV,vector popV) {\
        if(pushV.size()!=popV.size())return false;
        stackst;
        int i=0;
        for(int num:pushV){
            st.push(num);
            while(!st.empty()&&st.top()==popV[i]){
                st.pop();
                i++;
            }
        }
        return st.empty();
    }
}
// 关注TechGuide，大厂笔经面经闪电速递！

创作不易，你的鼓励是我创作的动力，如果你有收获，点个赞吧👍