专栏文章

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

vvscdr_
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min3yzsr
此快照首次捕获于
2025/12/01 20:11
3 个月前
此快照最后确认于
2025/12/01 20:11
3 个月前
查看原文

提醒

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

思路

让栈stk边push 要读入的数，然后while，只要栈不为空且栈顶 == poped[j] ,那么久j++且stk.pop()
j是目前是第几个输出的数
为什么要这样呢，因为有些数出的数需要等再输入一些数并把它们输出后，栈经过pop，才能到达这个数并将其输出，所以我们如果边输入边判断而不是while往回找的话是无法处理这些数的，还要再取多次的处理，非常麻烦，所以边输入边while往回找才是最优解

代码

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...