这是上海计算机学会竞赛
P
473
P473
P473:栈的判断(
2021
2021
2021年
8
8
8月月赛 丙组
T
4
T4
T4)
标签:栈
题意:给定
n
n
n个数字,已知这些数字的入栈顺序为
1
,
2
,
3...
,
n
1,2,3...,n
1,2,3...,n,给定一个出栈顺序
a
1
,
a
2
,
a
3
.
.
.
,
a
n
a_1,a_2,a_3...,a_n
a1,a2,a3...,an,判断出栈顺序是否合法。合法输出
V
a
l
i
d
Valid
Valid,不合法输出
I
n
v
a
l
i
d
Invalid
Invalid。(
1
<
=
n
<
=
1
0
5
1<=n<=10^5
1<=n<=105)
题解:经典的出栈合法性判断。按入栈顺序正常入栈,当栈顶的元素和目前出栈顺序序列
a
a
a的第
k
k
k个相同的时候,不断地去出栈,同时把这个出栈下标
k
k
k往后移动,直到栈为空为止。(可以自己手动模拟一遍样例就比较好理解了)
代码:
#include <bits/stdc++.h>
using namespace std;
int a[100005], n, k = 1;
stack<int> s;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
s.push(i); // 入栈
while (s.top() == a[k]) {
s.pop(); k++; // 出栈
if (s.empty()) break;
}
}
if (s.empty()) cout << "Valid";
else cout << "Invalid";
return 0;
}