算法1:手写栈-模拟() $O(k*n)$
//出栈合法性判断,多了一个限制,栈的容量是限定了
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int stk[N], n, m, k, a[N];
int main() {
scanf("%d%d%d", &m, &n, &k);
while (k--) {
for (int i = 0; i < n; ++ i) scanf("%d", &a[i]);
int tt = 0, f = 1;
for (int i = 1, j = 0; i <= n; ++ i) {
stk[++tt] = i; //先进栈,按顺序进栈
if (tt > m) { //容量超过,非法
f = 0;
break;
}
while (tt && stk[tt] == a[j]) { //只要当前栈顶元素和出栈序列匹配就一直出
tt--;
j++;
}
}
if (tt) f = 0;
if (f) printf("YES\n");
else printf("NO\n");
}
return 0;
}
算法2:stl容器-模拟() $O(k*n)$
//出栈合法性判断,多了一个限制,栈的容量是限定了
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m, k, a[N];
bool check() {
stack<int> stk;
for (int i = 1, j = 0; i <= n; ++ i) {
stk.push(i);
if (stk.size() > m) return false;
while (stk.size() && stk.top() == a[j]) {
stk.pop();
j++;
}
}
return stk.empty();
}
int main() {
scanf("%d%d%d", &m, &n, &k);
while (k--) {
for (int i = 0; i < n; ++ i) scanf("%d", &a[i]);
if (check()) printf("YES\n");
else printf("NO\n");
}
return 0;
}
算法3:模拟3() $O(k*n)$
//从出栈元素分析,x要出栈,则小于它的数必然都需要入栈
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m, k, a[N];
int stk[N], x;
int main() {
scanf("%d%d%d", &m, &n, &k);
while (k--) {
int tt = 0, j = 1, f = 1; //j用来表示当前要入栈的值
for (int i = 0; i < n; ++ i) {
scanf("%d", &x); //x要出栈,此时栈顶元素小于x,就需要入栈,x才能入栈后再出栈
while (!tt || stk[tt] < x && tt < m) stk[++tt] = j++;
if (stk[tt] == x) tt--;
else f = 0;
}
if (f) printf("YES\n");
else printf("NO\n");
}
return 0;
}