P4387 【深基15.习9】验证栈序列 题解记录

vscdr_ · 2025-11-20 20:54:20 · 个人记录

提醒

这题其实没那么复杂，别把它想的太复杂了

思路

让栈stk边push 要读入的数，然后while，只要栈不为空且栈顶 == poped[j] ,那么久j++且stk.pop()
j是目前是第几个输出的数

为什么要这样呢，因为有些数出的数需要等再输入一些数并把它们输出后，栈经过pop，才能到达这个数并将其输出，所以我们如果边输入边判断而不是while往回找的话是无法处理这些数的，还要再取多次的处理，非常麻烦，所以边输入边while往回找才是最优解

代码

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 100007;
stack<int> stk;
int t, n;
int pushh[N], popp[N];
int main()
{
    cin >> t;
    while (t--)
    {
        while (stk.size())
            stk.pop();
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            cin >> pushh[i];
        }

        for (int i = 1; i <= n; i++)
        {
            cin >> popp[i];
        }
        int j = 1;
        for (int i = 1; i <= n; i++)
        {
            stk.push(pushh[i]);
            while (stk.size() && stk.top() == popp[j])
            {
                j++;
                stk.pop();
            }
        }
        if (j == n + 1)
        {
            cout << "Yes";
        }
        else
        {
            cout << "No";
        }
        putchar('\n');
    }
    return 0;
}