PTA：出栈序列的合法性

题目

给定一个最大容量为 M 的堆栈，将 N 个数字按 1, 2, 3, …, N 的顺序入栈，允许按任何顺序出栈，则哪些数字序列是不可能得到的？例如给定 M=5、N=7，则我们有可能得到{ 1, 2, 3, 4, 5, 6, 7 }，但不可能得到{ 3, 2, 1, 7, 5, 6, 4 }

输入格式

输入第一行给出 3 个不超过 1000 的正整数：M（堆栈最大容量）、N（入栈元素个数）、K（待检查的出栈序列个数）。最后 K 行，每行给出 N 个数字的出栈序列。所有同行数字以空格间隔。

输出格式

对每一行出栈序列，如果其的确是有可能得到的合法序列，就在一行中输出YES，否则输出NO。

输入样例

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

思路

一些要注意的细节：

1. IsPopOrder 函数的作用：检查是否最终能够使堆栈为空。

如果最后堆栈为空，说明可以得到给定的出栈序列，否则无法得到。→ 只有在堆栈为空时才能够成功匹配所有入栈和出栈操作。

IsPopOrder 函数中使用了两个vector( pushV 和 popV) 来表示入栈和出栈序列。
在 main 函数中使用一个固定的 ts 向量（ts的内容题目中有说）来表示入栈序列，其中每个出栈序列都使用相同的入栈序列。这可能不符合题目要求，因为每个出栈序列可以有不同的入栈顺序。我们应该根据输入的 v 向量，将它们与 ts 向量一一对应。

2. 题目中指定堆栈的最大容量为 M，应该确保堆栈的大小不会超过 M。因此可以在 IsPopOrder 函数中添加对堆栈大小的检查。（代码第九行，while的第二个条件确保了堆栈大小不会超过最大容量 M）

代码

#include<iostream>
#include<vector>
#include<stack>
using namespace std;
bool IsPopOrder(vector<int>& pushV,vector<int>&popV,int M)
{
    stack<int> st;
    int pushi = 0,popi = 0;
    while(pushi<pushV.size() && st.size() < M)
    {
        st.push(pushV[pushi++]);
        while(!st.empty() && st.top() == popV[popi])
        {
            st.pop();
            popi++;
        }
    }
    return st.empty();
}

int main()
{
    int M,N,K;
    cin>>M>>N>>K;
    vector<int> ts;
    for(int k = 0;k<N;k++)
    {
        ts.push_back(k+1);
    }
    //M:最大容量, N:入栈元素个数, K:待检查的出栈序列个数
    for(int i = 0;i<K;++i)
    {
        //输入
        vector<int> v;
        for(int j =0;j<N;j++)
        {
            int tmp = 0;
            cin>>tmp;
            v.push_back(tmp);
        }
        //判断
        if(IsPopOrder(ts,v,M))
        {
            cout<<"YES"<<endl;
        }
        else
        {
            cout<<"NO"<<endl;
        }
    }
    return 0;
}