网站建设主流开发语言,西城区好的网站建设多少钱,wordpress调用自定义文章类型,深圳技术支持 骏域网站建设目录
力扣946. 验证栈序列
解析代码 力扣946. 验证栈序列
946. 验证栈序列
难度 中等
给定 pushed 和 popped 两个序列#xff0c;每个序列中的 值都不重复#xff0c;只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时#xff0c;返回 true每个序列中的 值都不重复只有当它们可能是在最初空栈上进行的推入 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 之前弹出。提示
1 pushed.length 10000 pushed[i] 1000pushed 的所有元素 互不相同popped.length pushed.lengthpopped 是 pushed 的一个排列
class Solution {
public:bool validateStackSequences(vectorint pushed, vectorint popped) {}
}; 解析代码 思路就是用栈来模拟进出栈的流程。 一直让元素进栈进栈的同时判断是否需要出栈。当所有元素模拟完毕之后如果栈中还有元素那么就是一个非法的序列。否则就是一个合法的序列。
class Solution {
public:bool validateStackSequences(vectorint pushed, vectorint popped) {if(pushed.size() ! popped.size())return false;stackint st;int i 0;for(auto e : pushed){st.push(e); // 不匹配就持续入匹配就持续出while(!st.empty() st.top() popped[i]){st.pop();i;}}// return i popped.size();return st.empty();}
};
