南通网站建设小程序,国外游戏商城网站欣赏,网站关于我们什么意思,胶州城乡建设局网站这是上海计算机学会竞赛 P 473 P473 P473#xff1a;栈的判断#xff08; 2021 2021 2021年 8 8 8月月赛 丙组 T 4 T4 T4#xff09;标签#xff1a;栈题意#xff1a;给定 n n n个数字#xff0c;已知这些数字的入栈顺序为 1 , 2 , 3... , n 1,2,3...,n 1,2,3...,n栈的判断 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 1n10^5 1n105题解经典的出栈合法性判断。按入栈顺序正常入栈当栈顶的元素和目前出栈顺序序列 a a a的第 k k k个相同的时候不断地去出栈同时把这个出栈下标 k k k往后移动直到栈为空为止。可以自己手动模拟一遍样例就比较好理解了代码
#include bits/stdc.h
using namespace std;int a[100005], n, k 1;
stackint 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;
}
