学习记录

# 问题

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列 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();
    }
}