题解 | 验证栈序列
验证栈序列
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,所有入栈操作完成后,如果栈为空,说明出栈序列合法,否则不合法。