一、题目输入两个整数序列第一个序列表示栈的压入顺序请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序序列45,3,2,1是该压栈序列对应的一个弹出序列但4,3,5,1,2就不可能是该压栈序列的弹出序列。二、大致思路思路借用一个额外的辅助栈举例入栈1,2,3,4,5出栈4,5,3,2,1遍历压栈顺序先将第一个放入栈中这里是1然后判断栈顶元素是不是出栈顺序的第一个元素这里是4很显然1≠4所以我们继续压栈直到相等以后开始出栈出栈一个元素则将出栈顺序向后移动一位直到不相等这样循环等压栈顺序遍历完成如果辅助栈还不为空说明弹出序列不是该栈的弹出顺序。首先1入辅助栈此时栈顶1≠4继续入栈2此时栈顶2≠4继续入栈3此时栈顶3≠4继续入栈4此时栈顶44出栈4弹出序列的位置向后移一位此时为5,辅助栈里面是1,2,3此时栈顶3≠5继续入栈5此时栈顶55出栈5,弹出序列向后一位此时为3,辅助栈里面是1,2,3….依次执行最后辅助栈为空。如果不为空说明弹出序列不是该栈的弹出顺序三、代码实现importjava.util.ArrayList;importjava.util.Stack;publicclassSolution{publicbooleanIsPopOrder(int[]pushA,int[]popA){if(pushA.length0||popA.length0||popA.length!pushA.length)returnfalse;StackIntegerstacknewStackInteger();intj0;for(inti0;ipushA.length;i){stack.push(pushA[i]);//入栈while(!stack.isEmpty()stack.peek()popA[j]){stack.pop();//出栈j;//弹出序列向后一位}}returnstack.isEmpty();}}
