题解 | 验证栈序列

验证栈序列

https://www.nowcoder.com/practice/d3178fe362dd4810b577c77c9e128fc5

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 = Integer.parseInt(in.nextLine());
        while (q-- > 0) {
            int n = Integer.parseInt(in.nextLine());
            int[] pushedArr = parseInput(in.nextLine(), n);
            int[] poppedArr = parseInput(in.nextLine(), n);

            Stack<Integer> stack = new Stack<>();
            int popIndex = 0;

            for (int num : pushedArr) {
                stack.push(num);
                // 这里必须是while不能是if,因为栈中可能已经存储了多个可被pop出的元素
                while (!stack.isEmpty() && stack.peek() == poppedArr[popIndex]) { 
                    stack.pop();
                    popIndex++;
                }
            }
            System.out.println(stack.isEmpty() ? "Yes" : "No");
        }
    }

    private static int[] parseInput(String input, int n) {
        String[] parts = input.split(" ");
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            result[i] = Integer.parseInt(parts[i]);
        }
        return result;
    }
}

用一个栈来模拟入栈和出栈过程。

1,顺序遍历入栈序列:每次将入栈序列的元素依次压入栈中。

2,尝试出栈:每次入栈后,检查栈顶元素是否等于当前出栈序列的下一个元素。如果相等,则弹出栈顶元素,并向右移动出栈序列指针,重复此过程直到不相等或栈为空。注意每次入栈后,尽可能多地进行出栈操作,即必须用while不能是if。

3,所有入栈操作完成后,如果栈为空,说明出栈序列合法,否则不合法。

全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务