题解 | #验证栈序列#

题目链接

题目描述

给定长度为 n 的入栈序列 pushed 和长度为 n 的出栈序列 popped，两者均为 1 到 n 的一个排列。初始时栈为空，只允许在栈顶进行插入（入栈）和删除（出栈）操作。若可通过若干操作使出栈顺序等于 popped，则称其为合法出栈序列。

现有 T 组测试，每组给定对应序列，判断 popped 是否为合法出栈序列。

输入描述: 第一行输入整数 T，表示测试组数。对于每组测试：

一行整数 n，表示序列长度。
一行 n 个整数，为入栈序列 pushed。
一行 n 个整数，为出栈序列 popped。

输出描述: 对于每组测试，输出一行。如果 popped 为合法出栈序列，则输出 Yes；否则输出 No。

解题思路

这是一个典型的栈模拟问题。我们可以借助一个辅助栈，来模拟整个入栈和出栈的过程，并检查是否能得到目标出栈序列。

算法步骤如下：

初始化：创建一个空栈 s 用于模拟，并创建一个指针 j (初始为0) 用于遍历出栈序列 popped。
遍历入栈序列：按顺序遍历给定的入栈序列 pushed 中的每一个元素。
模拟入栈：对于 pushed 中的当前元素 x，我们将其压入辅助栈 s 中。
模拟出栈：每当一个新元素入栈后，我们就检查栈顶元素是否与出栈序列 popped 中 j 指向的元素相同。
- 如果相同，说明此时可以进行一次出栈操作。我们便将栈顶元素弹出，并将 j 指针后移一位，表示 popped 序列中的这个元素已经被成功匹配。
- 这个检查和出栈的过程需要循环进行，直到栈为空或者栈顶元素不再与 popped[j] 匹配为止。
判断结果：遍历完整个 pushed 序列后，如果辅助栈 s 为空，说明 popped 序列中的所有元素都按照顺序被成功匹配和出栈了，因此是合法的出栈序列。反之，如果栈不为空，则说明是非法序列。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

bool is_valid_pop_order(int n, const vector<int>& pushed, const vector<int>& popped) {
    stack<int> s;
    int j = 0;
    for (int i = 0; i < n; ++i) {
        s.push(pushed[i]);
        while (!s.empty() && s.top() == popped[j]) {
            s.pop();
            j++;
        }
    }
    return s.empty();
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> pushed(n), popped(n);
        for (int i = 0; i < n; ++i) {
            cin >> pushed[i];
        }
        for (int i = 0; i < n; ++i) {
            cin >> popped[i];
        }
        if (is_valid_pop_order(n, pushed, popped)) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
    return 0;
}

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            int[] pushed = new int[n];
            int[] popped = new int[n];
            for (int i = 0; i < n; i++) {
                pushed[i] = sc.nextInt();
            }
            for (int i = 0; i < n; i++) {
                popped[i] = sc.nextInt();
            }

            if (isValidPopOrder(n, pushed, popped)) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
    }

    private static boolean isValidPopOrder(int n, int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int val : pushed) {
            stack.push(val);
            while (!stack.isEmpty() && j < n && stack.peek() == popped[j]) {
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }
}

def solve():
    n = int(input())
    pushed = list(map(int, input().split()))
    popped = list(map(int, input().split()))

    stack = []
    j = 0
    for x in pushed:
        stack.append(x)
        while stack and j < n and stack[-1] == popped[j]:
            stack.pop()
            j += 1
    
    if not stack:
        print("Yes")
    else:
        print("No")

t = int(input())
for _ in range(t):
    solve()

算法及复杂度

算法：栈模拟
时间复杂度： $\mathcal{O}(N)$ ，对于每组测试用例，pushed 数组中的每个元素都只会被压入栈和弹出栈一次。
空间复杂度： $\mathcal{O}(N)$ ，在最坏的情况下，pushed 数组中的所有元素都会被压入栈中，因此栈需要 N 的空间。