NowCoder
Topic describes
Enter two sequences of integers. The first sequence represents the push order of the stack. Determine whether the second sequence is the eject order of the stack. Assume that all the numbers pushed are not equal.
For example, sequence 1,2,3,4,5 is the pushdown sequence of a stack, sequence 4,5,3,2,1 is a corresponding ejection sequence of the pushdown sequence, but sequence 4,3,5,1 cannot be the ejection sequence of the pushdown sequence.
Their thinking
A stack is used to simulate the push-in eject operation.
import java.util.*;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
int len = pushA.length;
Stack<Integer> stack = new Stack<>();
for(int pushIndex = 0, popIndex = 0; pushIndex < len; pushIndex++) {
stack.push(pushA[pushIndex]);
while(popIndex < len && ! stack.isEmpty()
&& stack.peek() == popA[popIndex]) {
stack.pop();
popIndex++;
}
}
return stack.isEmpty();
}
}
Copy the code