怎么创建一个博客网站,软件下载网站排行,软件开发如何定价,南京江北新区包括哪些地方题目来源#xff1a;栈的压入、弹出序列_牛客题霸_牛客网 题目#xff1a;如下
输入两个整数序列#xff0c;第一个序列表示栈的压入顺序#xff0c;请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序#xf…题目来源栈的压入、弹出序列_牛客题霸_牛客网 题目如下
输入两个整数序列第一个序列表示栈的压入顺序请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序序列4,5,3,2,1是该压栈序列对应的一个弹出序列但4,3,5,1,2就不可能是该压栈序列的弹出序列。
答案如下
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param pushV int整型vector * param popV int整型vector * return bool布尔型*/bool IsPopOrder(vectorint pushV, vectorint popV) {// write code herestackint st;int pushi0,popi0;while(pushipushV.size()){st.push(pushV[pushi]);pushi;while(!st.empty()st.top()popV[popi]){st.pop();popi;}}return st.empty();}
};
解析如下
1建立栈和变量
题目是判断第二个序列是否可能为该栈的弹出顺序那么这里我们可以建立一个栈来模拟栈的压入和弹出
由于pushV和popV是vector可以用operator[]来进行访问那么我们可以创建变量pushi和popi用于访问pushV和popV
stackint st; int pushi0,popi0;
2模拟
假设pushV中有5个数据那么当pushi4的时候已经访问完pushV中的数据那么我们就可以以此为while循环判断条件即pushipushV.size()
将pushV中的数据逐个压入st栈中由于出栈的顺序未定判断是否符合popV序列那么可能入完第一个判断不符合再入第二个判断符合当st不为空时并且当st的栈顶数据等于popV的数据时就把st的栈顶数据pop掉有可能弹出完下一个数据仍可能在弹出数据中这时我们继续进行判断
如图所示 while(pushipushV.size()) { st.push(pushV[pushi]); pushi; while(!st.empty()st.top()popV[popi]) { st.pop(); popi; } }
3判断
当数据都弹出后st为空说明pushV中的数据对应有符合popV中的出栈顺序反之则没有
return st.empty(); 到这里我们讲解完毕
如果对您有帮助的话点一个免费的赞和收藏叭
由于作者水平不足如有任何错误请读者在评论区交流
