PTA出栈序列的合法性 

题目详情 - L2-1 出栈序列的合法性 (pintia.cn)

参考博客：【图解】L2-1 出栈序列的合法性 (25分)_l2-1 出栈序列的合法性 分_ChuanYang Chen的博客-CSDN博客

思路简述：

比如当我们输入一个4时，就说明这个数应该此时是作为栈顶元素，因此我们模拟一下，

把1-4数按顺序压入堆栈 

若栈不空且栈没有越界且栈顶元素就是num，我们就让栈顶元素出栈。

此时我们如果再输入7，我们把5-7压入堆栈，

此时栈不空且栈没有越界且栈顶元素就是num，我们让6出栈。

但如果我们输入一个5，无需再入栈元素

我们进入判断，栈顶元素不是5，出现错误，不合法！！

#include <bits/stdc++.h>
using namespace std;
int M,N,K,num,start,flag;
using namespace std;
int main(){cin>>M>>N>>K;for (int i=0;i<K;i++){stack<int>st;start = 1;flag = 1;for (int j=0;j<N;j++){cin>>num;while (start<=num)st.push(start++);//当前输入的数字是栈顶，我们补充栈 if (!st.empty()&&st.size()<=M&&num==st.top())st.pop();else flag = 0;}if (flag){cout<<"YES"<<endl;}else {cout<<"NO"<<endl;}}
}

栈与卡特兰数

栈和卡特兰数（Catalan number）_栈 卡特兰数_Ann's Blog的博客-CSDN博客

什么是合法的出栈序列， 凡是合法序列都遵循以下规律：即对于出栈序列中的每一个数字，在它后面的、比它小的所有数字，一定是按递减顺序排列的。 

所以到底有多少种合法序列呢？
答案就是：合法出栈数目==卡特兰数

h（0）=1，h（1）=1
h ( n ) = h ( 0 ) ∗ h ( n − 1 ) + h ( 1 ) ∗ h ( n − 2 ) + . . . + h ( n − 1 ) ∗ h ( 0 )         (n>=2)
 

#include<bits/stdc++.h>
using namespace std;
int h(int n)
{if(n==0||n==1) return 1;int hh=0;for(int i=0;i<n;i++){hh+=h(i)*h(n-1-i);//公式}return hh;
}
int main(){int n;cin>>n;cout<<h(n);return 0;
}