栈的弹出压入序列<难度系数⭐⭐>

举报
跳动的bit 发表于 2022/06/28 06:11:19 2022/06/28
【摘要】 📝 题述:输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列 1,2,3,4,5 是某栈的压入顺序,序列 4,5,3,2,1 是该压栈序列对应的一个弹出序列,但 4,5,3,2,1 就不可能是该压栈序列的弹出序列。⚠ 提示:0 <= pushV.length == popV.length <= 1000-1000 ...

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

⚠ 提示:

  • 0 <= pushV.length == popV.length <= 1000
  • -1000 <= pushV[i] <= 1000
  • pushV 的所有数字均不相同

💨示例1:

输入:
[1,2,3,4,5],[4,5,3,2,1]

返回值:
true

说明:
可以通过
push(1) => push(2) => push(3) => push(4) => pop() => push(5) => pop() => pop() => pop() => pop()
这样的顺序得到 [4,5,3,2,1] 这个序列,返回 true。

💨示例2:

输入:
[1,2,3,4,5],[4,3,5,1,2]

返回值:false

说明:
由于是 [1,2,3,4,5] 的压入顺序,[4,3,5,1,2] 的弹出顺序,要求 4,3,5 必须在 1,2 前压入,且 1,2 不能弹出,但是这样压入的顺序,1 又不能在 2 之前弹出,所以无法形成,返回 false。

🧷 平台:Visual studio 2017 && windows

🔑 核心思想:这道题之前我们有碰到过选择题。这道题本质就是模拟栈的特性 “Last In First Out”。

这里定义了一个栈来模拟,不管三七二十一,pushi 先入栈,随后 ++,出栈的顺序一定是入栈后再出的,所以每次入栈后都需要判断 pushi and popi 是否相等,相等就出(且要循环着出),否则就入,它们两个都能走到最后,就说明是匹配的。

在这里插入图片描述
nowcoder原题

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        stack<int> st;
        size_t pushi = 0, popi = 0;
        //压入顺序结束就必须出结果
        while(pushi < pushV.size())
        { 
            //先入一个数据,然后++
            st.push(pushV[pushi++]);
            //循环出栈
            while(!st.empty() && st.top() == popV[popi])
            {
                ++popi;
                st.pop();
            }
        }
        //st为空,说明匹配
        return st.empty();
        //同上
        //return popi == popV.size();
    }
}; 
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。