前言：如果我们尝试在网上搜索这个问题的话，大部分的搜索结果都会提到卡塔兰数，这个算法的思路在笔者看来十分新颖有趣，并且其计算方式极其简单，在此记录下。

栈的定义：

        首先让我们来了解/回顾一下“栈”这种数据结构。严谨的定义是栈（stack）是只允许在一端进行插入或删除操作的线性表。而形象的理解就是有一个狭窄的单开口盒子，后进入的元素会“阻塞”这个盒子，所以我们每次只能从这个盒子的最上面（栈顶）取出元素。因为最顶上的一定是最后面放进去的，因此栈有后入先出的特点。

出栈顺序：

        让我们回到这个经典问题“N个数依次入栈，出栈顺序有多少种？”，由于题目只限制了依次入栈，并没有限制一定要全部入栈才可以出栈，因此会有多种不同的出栈顺序。如对于依次入栈的a, b, c三个元素，我们可以先全部入栈再依次出栈，这样的结果就是c, b, a。当然我们也可以选择先入栈a，然后立即出栈a，再入栈b，出栈b，以此类推，因此这种情况下的结果就是a, b, c。有兴趣的读者可以继续推导下其他可能性，总共是有5种不同的排列。那么这个5是如何得出来的呢？下面就进入到本篇文章的正题了。

有趣的算法：

        首先我们从整体看栈的行为，有入栈就必定有出栈，即如果把入栈和出栈看作一种行为的话，对于N个数来说，存在着2N个行为。

        我们把入栈记录为1，出栈记录为0，则寻找出栈顺序种类的问题转化为了寻找有效的2N数字排序。

        我们先不论该序列是否有效：对于N个1与N个0的排序，很简单有C(2n,n)种。

        然后我们讨论什么是有效：很显然，必须先有入栈才能有出栈，即从头开始的任意长序列中1的数量必定比0多。我们既然已经知道了任意排列的总数，那么只需要找到无效序列数量，将其减去即可。而对于某个无效序列，必定存在某一2m+1长度中，存在m个1，m+1个0（即出栈次数大于入栈次数）。这时我们截取这一长度序列作为左序列，而右序列剩下的数字中显然1比0多一位。于是我们将右序列中的1与0互换，与左序列拼合，则这一新序列由n+1个0与n-1个1组成，即存在该无效序列对于新序列的某种映射关系，并且该关系对任意一个无效序列均成立。

        然后我们来分析下新序列：对于任意n+1个0与n-1个1组成的序列，由于0的个数多2个，2n为偶数，故必在某一个奇数位上出现0的累计数超过1的累计数，也即总是存在某一2m+1长度上，存在m个1，m+1个0。我们截取这一长度序列作为左序列，显然它与无效序列的左序列是完全一致的。我们观察剩下的数字，其中0的数量比1的多一个，也即无效序列的右部分处理后的状态。于是我们得出无效序列与新序列存在一一映射关系，也即求无效序列的种类数量就转变成了求新序列的种类数量。显然新序列的数量就是简单的组合数 C(2n,n+1)

        这样我们就得到了最终的结果 输出序列的总数目=C(2n,n)-C(2n,n+1)=C(2n,n)/(n+1)

        Q：如何证明这两种序列是一一对应的？

        A：假设非法序列为 A，对应的序列为 B。对于任意一个A，总能通过上述的映射关系找到唯一的B，同样的，对于任意一个B，有且仅有一个A与之对应，这样就可以说他们是一一对应的映射关系。

参考网址：

https://developer.aliyun.com/article/35562 

https://zhuanlan.zhihu.com/p/97619085