题目描述

关系

内容

给定一个最多能存 $M$ 个数字的栈，将 $1\sim N$ 按顺序压入栈中，过程中可随机弹出栈顶元素。

当 $N$ 个数字都经历过入栈和出栈后，我们按照元素出栈的顺序，可以得到一个弹出序列。

现在给定一系列 $1\sim N$ 的随机排列序列，请你判断哪些序列可能是该栈的弹出序列。

例如，当 $N=7,M=5$ 时，1, 2, 3, 4, 5, 6, 7 可能是该栈的弹出序列，而 3, 2, 1, 7, 5, 6, 4 不可能是该栈的弹出序列。

输入格式

第一行包含三个整数 $M,N,K$，分别表示栈的容量，数字个数，需要判断的序列个数。

接下来 $K$ 行，每行包含一个 $1\sim N$ 的排列。

输出格式

对于每个序列，如果可能是该栈的弹出序列，则输出一行 YES，否则输出一行 NO。

数据范围

$1\le M,N,K\le 1000$

输入样例：

5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2

输出样例：

YES
NO
NO
YES
NO

问题分析

最初思路

这道题和 42-栈的压入、弹出序列的本质是一样的，无非是这个栈是有上限的，我们不能无限的压栈。我们还是按照输入序列从左到右进行模拟。

如果栈的空间足够，即栈的容量 ${\displaystyle M\ge N}$，那么就是 42-栈的压入、弹出序列一样的思路。如果 ${\displaystyle M<N}$，那么我们还需要判断栈是否已经满。如果栈已经满了，那么在下一个数进来之前，必须先弹出栈顶的数，如果栈顶不与弹出序列相同，就可以直接返回 false 了。

思路分析

执行流程设计

总结

代码实现

#include <bits/stdc++.h>
using namespace std;

const int N = 1010, M = 1010;
int n, m, k, tt = -1;
int b[N], stk[M];

void solve() {
    bool flag = true;
    int i = 0;
    for (int in = 1; in <= n; in++) {
        if (tt == m - 1 && stk[tt] != b[i]) {
            flag = false;
            break;
        } else {
            stk[++tt] = in;
        }
        
        while (tt >= 0 && stk[tt] == b[i]) {
            tt--;
            i++;
        }
    }
    
    
    if (!flag) cout << "NO" << endl;
    else {
        if (tt < 0) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

int main()
{
    cin >> m >> n >> k;
    while (k--) {
        for (int i = 0; i < n; i++) cin >> b[i];   
        solve();
        memset(stk, 0, sizeof stk);
        tt = -1;
    }
    return 0;
}