题目描述

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

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

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

例如，当 N=7,M=5 时，1, 2, 3, 4, 5, 6, 7可能是该栈的弹出序列，而 3, 2, 1, 7, 5, 6, 4 不可能是该栈的弹出序列。
输入格式
第一行包含三个整数 M,N,K，分别表示栈的容量，数字个数，需要判断的序列个数。

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

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

数据范围
1≤M,N,K≤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

思想：如果要弹出一个数，那么说明比它小的数字已经进栈了，所以要在一个数num输入之后把比它小的数都输入到栈中，用val表示输进去的数的大小，val不断++，直到栈满或者val==num时结束入栈操作。如果val==num，将这个值弹出，否则说明整个序列存在问题，把flag变为false，输出结果。

算法1

(调用STL栈) $797ms$

时间相对较长，但好理解。

C++ 代码

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

int main()
{   
    int m,n,k;
    scanf("%d%d%d",&m,&n,&k);

    while(k--)
    {
        stack<int> stk;
        int val=1;
        bool flag = true;;
        for(int i=0;i<n;i++)
        {
            int num; scanf("%d",&num);
            while(stk.empty() || (stk.top() < num && stk.size() < m))
            {
                stk.push(val++);
            }
            if(stk.top() == num) stk.pop();
            else flag = false;
        }
        if(flag==false) printf("NO\n");
        else printf("YES\n");
    }

    return 0;
}

算法2

(数组模拟栈) $310ms$

对STL进行修改而来，速度更快。

C++ 代码

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

int main()
{   
    int m,n,k;
    scanf("%d%d%d",&m,&n,&k);

    while(k--)
    {
        int stk[m],tt=0;
        int val=1;
        bool flag = true;;
        for(int i=0;i<n;i++)
        {
            int num; scanf("%d",&num);
            while(tt==0 || (stk[tt] < num && tt < m))
            {
                stk[++tt] = val++;
            }
            if(stk[tt] == num) tt--;
            else flag = false;
        }
        if(flag==false) printf("NO\n");
        else printf("YES\n");
    }

    return 0;
}