思路:

  • 题目要我们判断两个序列是否符合入栈出栈的次序,我们就可以用一个栈来模拟。对于入栈序列,只要栈为空,序列肯定要依次入栈。那什么时候出来呢?自然是遇到一个元素等于当前的出栈序列的元素,那我们就放弃入栈,让它先出来。
//入栈:栈为空或者栈顶不等于出栈数组
while(j < n && (s.isEmpty() || s.peek() != popA[i])){
    s.push(pushA[j]);
    j++;
}

  • 如果能按照这个次序将两个序列都访问完,那说明是可以匹配入栈出栈次序的。

具体做法

  • step 1:准备一个辅助栈,两个下标分别访问两个序列。
  • step 2:辅助栈为空或者栈顶不等于出栈数组当前元素,就持续将入栈数组加入栈中。
  • step 3:栈顶等于出栈数组当前元素就出栈。
  • step 4:当入栈数组访问完,出栈数组无法依次弹出,就是不匹配的,否则两个序列都访问完就是匹配的。 alt

代码

import java.util.*;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer> stack=new Stack<>();
        int j=0;
        int n=pushA.length;
      	//遍历出栈元素
        for(int i=0;i<n;i++){
          //只要 值不等于出栈元素就入栈 
          //遍历入栈
            while(j<n&&(stack.isEmpty()||stack.peek()!=popA[i])){
                stack.push(pushA[j]);
                j++;
            }
          //栈顶等于出栈元素就出栈
            if(stack.peek()==popA[i]){
                stack.pop();
            }
          //不相等直接返回false
            else{
                return false;
            }
            
        }
        return true;
      
    }
}