关于卡特兰数的一种思考

卡特兰数的一种思考"/>

关于卡特兰数的一种思考

问题：   如果进栈顺序123，出栈顺序是312，它的顺序是+1+2+3-3-1-2（+1+1+1-1-1-1），它的前缀和大于等于0，但它也是个非法出栈序列，这是为什么？

在考虑整个问题的过程中，关注点在于入栈和出栈（操作类型），而不在于谁入栈或者谁出栈（具体操作），也就是说那个2n长度的序列，我们只考虑哪个位置是+哪个位置是-，因为入栈的相对顺序（重点：相对顺序）已经确定了，一定是12345...n，

那么我的这个序列只要合法，它出栈的结果就已经唯一确定了（也就是说你的那个顺序+++---，唯一的可能就是321，而不会是其他的）

而如果这个序列不合法，说明在整个过程中，出现了栈已经空了，但是还要出栈。

题目已经给定了入栈的顺序一定是123...n，也就是说那个2n长度的序列按顺序把+号提取出来，就是+1+2,,,,+n，如果序列P合法，那么P所对应的出栈顺序是唯一的，至于哪个-号对应的是哪个数据出栈，你只需要按照序列操作一遍就得到了，而这个结果就是唯一的， 那么对于+++---，操作一遍你就会发现，只会出来321，若出栈顺序是312，你会发现你找不到一个合法的序列去实现这个，所谓的合法与非合法，并不是直接说你的这个序列合法不合法，而是说你整个出栈入栈的操作过程合法不合法（即有没有出现前缀和<0），如果合法，那么它所对应的唯一序列也合法，如果不合法，那么序列你都找不到。

因为操作合法，所以序列合法，究其本质还是一个因果关系。

这是在知乎上看了关于leetcode发布的卡特兰数问题以及一些网友疑问的一些思考，欢迎广大网友讨论指正