行业知识
剑指offer面试题31:栈的压入、弹出序列
2026-11-18 13:31:34
来源:互联网转载
面试题31:栈的压入、弹出序列
题目:
���定 pushed 和 popped 两个序列,每个序列中的 值都不重复,只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时,返回 true;否则,返回 false 。
()示例1:
输入:pushed = [1,2,3,4,5], popped = [4,5,3,2,1]输出:true解释:我们可以按以下顺序执行:push(1), push(2), push(3), push(4), pop() -> 4,push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
示例2:
()输入:pushed = [1,2,3,4,5], popped = [4,3,5,1,2]输出:false解释:1 不能在 2 之前弹出。
思路:
这个题目我们可以模拟整个入栈和出栈的操作,我们按照建立一个栈,按照pushed序列压入栈,并且判断是否与popped序列的首元素是否相同,如果相同就把这个元素从栈内弹出,并观察下一个popped元素判断与现在的栈元素首元素是否相同,如果是则循环操作,直到遇到与栈首元素不同或者栈为空时退出循环,继续在外边接着上面pushed序列压入剩余元素,等遍历完所有pushed元素后,如果两个序列相互匹配的话就栈内为空,否则就不为空。
代码:
class Solution {public: bool validateStackSequences(vector& pushed, vector& popped) { stack st; int n = pushed.size(); for(int i=0,j=0;i//循环遍历pushed元素 st.emplace(pushed[i]);//也可以用s1.push(pushed[i]); while(!st.empty()&&st.top()==popped[j]){//判断popped元素与栈顶元素是否相同 st.pop(); j++; } } return st.empty(); }};
上一篇:提升下载速度的解决方案
下一篇:软件服务器应该怎么选择?