【一刷《剑指Offer》】面试题 22:栈的压入、弹出系列

简介: 【一刷《剑指Offer》】面试题 22:栈的压入、弹出系列

力扣对应题目链接:946. 验证栈序列 - 力扣(LeetCode)

牛客对应题目链接:栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com)

核心考点 :栈的理解。


一、《剑指Offer》内容


二、分析题目

要判定第二个序列是否可能是该栈的弹出序列,就要使用指定的入栈顺序模拟出来对应的弹栈序列,我们设入栈顺序序列式 pushV,可能出栈序列 popV。

popv 的第一个元素,一定是最后入栈,最先弹栈的, 而我们的入栈顺序是一定的,也就决定了,我们必须一直入栈,直到碰到 popv 的第一个元素,然后开始弹栈。最后在循环这个过程,如果符合要求,最后栈结构一定是空的。

  1. 遍历入栈序列,只要 popv 的第一个数据和当前 pushv 的数据不相等,一直进行入栈操作。
  2. 只要 st 栈顶值和 popv 的出栈序列数据是相等的,则一直执行出战逻辑
  3. 返回 st.empty()

三、代码

//牛客
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param pushV int整型vector 
     * @param popV int整型vector 
     * @return bool布尔型
     */
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        if(pushV.empty() || popV.empty() || pushV.size()!=popV.size())
            return false;
        stack<int> st;
        int j=0;
        for(int i=0; i<pushV.size(); i++)
        {
            st.push(pushV[i]);
            while(!st.empty() && st.top()==popV[j])
            {
                st.pop();
                j++;
            }
        }
        if(st.empty()) return true;
        else return false;
    }
};
 
//力扣
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        if(pushed.empty() || popped.empty() || pushed.size()!=popped.size())
            return false;
        stack<int> st;
        int j=0;
        for(int i=0; i<pushed.size(); i++)
        {
            st.push(pushed[i]);
            while(!st.empty() && st.top()==popped[j])
            {
                st.pop();
                j++;
            }
        }
        return st.empty();
    }
};


相关文章
|
24天前
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
|
25天前
|
算法
【一刷《剑指Offer》】面试题 21:包含 main 函数的栈
【一刷《剑指Offer》】面试题 21:包含 main 函数的栈
|
25天前
【一刷《剑指Offer》】面试题 20:顺时针打印矩阵
【一刷《剑指Offer》】面试题 20:顺时针打印矩阵
|
25天前
【一刷《剑指Offer》】面试题 19:二叉树的镜像
【一刷《剑指Offer》】面试题 19:二叉树的镜像
|
25天前
【一刷《剑指Offer》】面试题 18:树的子结构
【一刷《剑指Offer》】面试题 18:树的子结构
|
25天前
【一刷《剑指Offer》】面试题 17:合并两个排序的链表
【一刷《剑指Offer》】面试题 17:合并两个排序的链表
|
25天前
【一刷《剑指Offer》】面试题 16:反转链表
【一刷《剑指Offer》】面试题 16:反转链表
|
25天前
【一刷《剑指Offer》】面试题 15:链表中倒数第 k 个结点
【一刷《剑指Offer》】面试题 15:链表中倒数第 k 个结点
|
25天前
|
C++
【一刷《剑指Offer》】面试题 14:调整数组顺序使奇数位于偶数前面
【一刷《剑指Offer》】面试题 14:调整数组顺序使奇数位于偶数前面
|
25天前
|
机器学习/深度学习
【一刷《剑指Offer》】面试题 13:在 O(1) 时间删除链表结点
【一刷《剑指Offer》】面试题 13:在 O(1) 时间删除链表结点