经典问题——验证栈序列

我们先来看题目描述给定 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 之前弹出。提示1 pushed.length 1000 0 pushed[i] 1000 pushed 的所有元素互不相同 popped.length pushed.length popped 是 pushed 的一个排列。解析只要模拟入栈和出栈的过程将一个数进行入栈操作的时候检查该数是否为下一个要出栈的数如果是就弹出该数并继续检查栈中的数。如果能扫描完所有要出栈的数就是一个合法的栈序列。Java 代码实现使用 ArrayList 模拟栈class Solution { public boolean validateStackSequences(int[] pushed, int[] popped) { ListInteger Snew ArrayList(); int j0; for(int i0;ipushed.length;i){ S.add(pushed[i]); while(S.size()0jpopped.lengthS.get(S.size()-1)popped[j]){ S.remove(S.size()-1); j; } } return jpopped.length; } }C 代码实现直接用 STL stack class Solution { public: bool validateStackSequences(vectorint pushed, vectorint popped) { stackintS; int npushed.size(); int j0; for(int i0;in;i){ S.push(pushed[i]); while(S.size()0jnS.top()popped[j]){ S.pop(); j; } } return jn; } };