题解 | 验证栈序列

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

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int q = in.nextInt(); // 测试组数
        while (q-- > 0) {
            int n = in.nextInt();
            int[] pushed = new int[n];
            int[] popped = new int[n];
            for (int i = 0; i < n; i++) pushed[i] = in.nextInt();
            for (int i = 0; i < n; i++) popped[i] = in.nextInt();

            System.out.println(isValidPopOrder(pushed, popped) ? "Yes" : "No");
        }
    }

    public static boolean isValidPopOrder(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int j = 0; // popped 的指针

        for (int x : pushed) {
            stack.push(x);
            // 匹配栈顶和 popped[j]
            while (!stack.isEmpty() && stack.peek() == popped[j]) {
                stack.pop();
                j++;
            }
        }

        return stack.isEmpty();
    }
}