题解

按给定顺序依次把 pushed[i] 压栈。

每压入一个元素后，只要：

栈不空 && 栈顶 == popped[j]

就立刻弹出，并让 j++。

最后如果 j==n，说明目标序列全部成功匹配。

关键点：不能先把所有元素全部压栈，因为合法过程允许“入栈、出栈”交替进行。

时间复杂度 $O(n)$。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> pushed(n), popped(n);
    for (int &x : pushed) cin >> x;
    for (int &x : popped) cin >> x;

    stack<int> st;
    int j = 0;

    for (int x : pushed) {
        st.push(x);
        while (!st.empty() && j < n && st.top() == popped[j]) {
            st.pop();
            ++j;
        }
    }

    cout << (j == n ? "Yes" : "No") << '\n';
    return 0;
}