题解 | 验证栈序列

import java.util.Scanner;
import java.util.Stack;

/**
 * @author supermejane
 * @date 2025/10/1
 * @description
 */

public class Main {

    private static Stack<Integer> stack = new Stack<>();

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int pairNum = in.nextInt();
            for (int i = 0; i < pairNum; i++) {
                int singleLength = in.nextInt();
                int[] inSeq = new int[singleLength], outSeq = new int[singleLength];
                for (int j = 0; j < singleLength; j++) {
                    inSeq[j] = in.nextInt();
                }
                for (int j = 0; j < singleLength; j++) {
                    outSeq[j] = in.nextInt();
                }
                System.out.println(validate(inSeq, outSeq) ? "Yes" : "No");
                stack.clear(); //注意要clear
            }
        }
    }
	
  	//重点在于把情况分清楚就行
    public static boolean validate(int[] in, int[] out) {

        int i = 0;
        int j = 0;
        while (i < out.length) {
            int currentOut = out[i];
            if (!stack.isEmpty()) {
                if (!(stack.peek() == currentOut)) {
                    if (stack.contains(currentOut)) return false;
                    else {
                        while (j < in.length && in[j] != currentOut) {
                            stack.push(in[j++]);
                        }
                        if(j == in.length) return false;
                        if (in[j] == currentOut) {
                            j++;
                            i++;
                        }
                    }
                } else {
                    stack.pop();
                    i++;
                }
            } else {
                while (j < in.length && in[j] != currentOut) {
                    stack.push(in[j++]);
                }
                if(j == in.length) return false;
                if (in[j] == currentOut) {
                    j++;
                    i++;
                }
            }
        }
        return true;
    }
}