本文主要是介绍验证栈序列——使用O(n)的时间复杂度来判断出栈顺序是否正确,值得一看,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目描述
给出两个序列 pushed 和 poped 两个序列,其取值从 1 到 n(n≤100000)。已知入栈序列是 pushed,如果出栈序列有可能是 poped,则输出 Yes
,否则输出 No
。为了防止骗分,每个测试点有多组数据。
输入格式
第一行一个整数 q,询问次数。
接下来 q 个询问,对于每个询问:
第一行一个整数 n表示序列长度;
第二行 n 个整数表示入栈序列;
第三行 n 个整数表示出栈序列;
输出格式
对于每个询问输出答案。
样例 #1
样例输入 #1
2
5
1 2 3 4 5
5 4 3 2 1
4
1 2 3 4
2 4 1 3
样例输出 #1
Yes
No
解题思路
这道题其实就跟列车调度比较像,只不过那道题的数据范围比较小,可以用O(n^2)的时间复杂度来过,说白了就是有点水,而且它入栈的顺序就是一个递增的数列,是具有特殊性的,但是这道题就不一样了,这道题的数据范围比较大,很容易超时,所以我们要用一个O(n)的方法来过。
这个地方我们就可以来模拟出栈的过程,因为有些元素有可能是push进去后就直接弹出了,所以我们就可以基于此来进行判断:每次push进去一个元素时,就判断此时的栈顶和当亲应该pop的值是不是一个值,如果是,就将它弹出,然后继续判断,直到不是(此处可以用while循环)。
这样的操作结束后,就去查看栈,如果栈不为空,相当于就是说有元素没有出栈,就是不行的,所以输出“NO“,如果栈为空,那么就是正确的,输出”YES“.。
这里还有个点要注意,就是他有n次询问,所以每次结束后,要清空栈,否则就要出大事。
ACcode
#include <bits/stdc++.h>
using namespace std;
int a[1000003], b[1011010];
stack <int> s;int main() {ios::sync_with_stdio(false);//提速小妙招int t;cin >> t;for (int i = 0; i < t; i++) {int n;cin >> n;int cnt = 0;for (int i = 0; i < n; i++) {cin >> a[i];}for (int i = 0; i < n; i++) {cin >> b[i];}for (int i = 0; i < n; i++) {s.push(a[i]);while (s.top() == b[cnt]) {s.pop();cnt++;if (s.empty()) {break;}}}if (s.empty()) {cout << "Yes" << endl;} else {cout << "No" << endl;}while (!s.empty())s.pop();}return 0;
}
跪谢陈厚节老师提供思路
看了这么久,作者也写了这么久,能不能点一个赞,在收藏一下呢?最好的话在点个关注吧
谢谢啦!
这篇关于验证栈序列——使用O(n)的时间复杂度来判断出栈顺序是否正确,值得一看的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!