【深基15.习9】验证栈序列

题意

给出入栈序列 pushed 和出栈序列 poped。

判断 poped 是否可能是按照栈的先进后出规则，由 pushed 模拟得到的出栈序列。

思路

最直接的做法是递归枚举每一步是“入栈”还是“出栈”。

这个版本只适合小数据验证：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> pushed, poped;
vector<int> st;

bool dfs(int i, int j) {
    if (j == n) return true;
    if (!st.empty() && st.back() == poped[j]) {
        int x = st.back();
        st.pop_back();
        if (dfs(i, j + 1)) return true;
        st.push_back(x);
    }
    if (i < n) {
        st.push_back(pushed[i]);
        if (dfs(i + 1, j)) return true;
        st.pop_back();
    }
    return false;
}

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

    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        pushed.resize(n);
        poped.resize(n);
        for (int i = 0; i < n; i++) cin >> pushed[i];
        for (int i = 0; i < n; i++) cin >> poped[i];
        st.clear();
        cout << (dfs(0, 0) ? "Yes" : "No") << '\n';
    }

    return 0;
}

但这题其实不需要搜索。

因为栈的行为是确定的：

先按 pushed 顺序入栈；
每次只要栈顶和 poped 当前元素相同，就立刻出栈。

所以只需要一个栈和一个指针 j：

遍历 pushed 中的每个元素；
先把它压入栈；
然后只要栈顶等于 poped[j]，就持续弹栈；
最后如果栈为空，说明 poped 合法。

Python 知识

普通列表就是竞赛中最常用的栈：append 压栈，pop 弹栈，stack[-1] 访问栈顶。
tokens 整数迭代器连续读取多组不同长度的数据。
while stack and ... 利用短路顺序保证空栈时不会访问 stack[-1]。
/home/rainboy/mycode/hugo-blog/content/program_language/python/oj_input_output_cheatsheet.md：token 迭代读取多组数据。
/home/rainboy/mycode/hugo-blog/content/program_language/python/generator_expression.md：短路条件与可迭代数据。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22import sys


tokens = iter(map(int, sys.stdin.buffer.read().split()))
answers = []

for _ in range(next(tokens)):
    n = next(tokens)
    pushed = [next(tokens) for _ in range(n)]
    popped = [next(tokens) for _ in range(n)]
    stack = []
    next_pop = 0

    for value in pushed:
        stack.append(value)
        while stack and next_pop < n and stack[-1] == popped[next_pop]:
            stack.pop()
            next_pop += 1

    answers.append("Yes" if not stack else "No")

print("\n".join(answers))

复杂度

时间复杂度： $O(n)$
空间复杂度： $O(n)$

总结

这题的核心是“模拟栈的真实行为”，而不是枚举所有可能操作。

只要栈顶一旦能匹配目标出栈序列，就应该立刻出栈。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

【深基15.习9】验证栈序列

目录

题意

思路

Python 知识

代码

复杂度

总结

一图流解析