剑指Offer学习 栈的压入、弹出序列

学习记录

问题

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列 1,2,3,4,5 是某栈的压入顺序，序列 4,5,3,2,1 是该压栈序列对应的一个弹出序列，但 4,3,5,1,2 就不可能是该压栈序列的弹出序列。

理解

要想判断出第二个序列是否是该栈的弹出序列，我们得先模拟栈的压入。通过第一个序列，我们可以进行压栈。
引入一个辅助栈，接着依次扫描第一个序列A，然后将扫描到的数字压入辅助栈，判断当前栈中栈顶数字（即，最后进的数字）是否与第二个序列B中依次扫描的数字相等，若相等，则出栈；B中继续往后扫描。
若B是弹出序列，则辅助栈中应该是没有数字剩下；若栈中仍有内容，则B非弹出序列。

代码

import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer> temp = new Stack<>();
        int n = pushA.length;
        for(int indexA = 0, indexB = 0; indexA < n; indexA++) {
            temp.push(pushA[indexA]);
            while(indexB < n && temp.peek() == popA[indexB]) {
                temp.pop();
                indexB++;
            }
        }
        return temp.isEmpty();
    }
}