上一页我们把元素压进栈、弹出来，顺序会反过来。那如果允许「压一个、弹一个」交替进行呢？就像发牌人发一张就能打一张，出来的顺序就不止一种了。

用 n=3 走一遍完整混洗：进进进出进出，看 2 3 1 怎么诞生。

每个操作序列唯一确定一个混洗结果；对比 312 与 231 两条链，看 push/pop 交错顺序如何决定输出。

上一页我们已经确认：每一次栈混洗，都唯一对应一串 push 和 pop 操作。要数清楚有多少种混洗，最自然的想法是把每种操作序列当成一个符号串，先弄清「哪些串是合法的」，再数合法串的个数。

上一页我们数了 n=3 时共有 16 条合法操作序列，但其中两条会撞出相同的混洗——合法混洗其实只有 5 种。那 n=4、n=5 呢？逐个枚举太笨了，数学家找到了一个通用的计数公式。

中心是混洗对象，五个分支是 n=3 的全部合法输出序列，外加一个禁例做对照。

上一页我们枚举了 n=3 的五种混洗。但 3 个元素的排列明明有 3!=6 种——多出来的那一个是谁？把两份清单并排放一起对比，缺失的那个立刻现形。

上页我们数出了 n=3 只有 5 种混洗，全排列 6 种里恰好有一种「混不出来」。它长什么样？把 abc 变成 cab 时，先弹 c 再弹 a 就卡住了——因为 b 还压在 a 上面。这个卡住的形状叫 312 模式。

逐步推演：想最先输出 3，1 和 2 只能先被压进栈里。

跟着流程走一遍：取序列、枚举子序列、比对 312 模式，看判定如何落地。

用辅助栈逐个压入 1..n，贪心对齐目标序列，即可判定混洗合法性。

用一段 20 行的贪心模拟，把上一页的甄别策略变成可运行的判定程序。

高亮行正是贪心策略：能进栈就进栈，栈顶等于目标就弹出，两边都不满足则命中禁形 312。

上一页我们用栈模拟甄别混洗序列。现在换个视角：把每个 push 写成左括号「(」，pop 写成右括号「)」，一段操作序列就变成一串括号——而合法混洗，恰好对应合法匹配。

入栈顺序为 1,2,3,4，下列哪个出栈序列是合法的栈混洗？

• ✓n 个元素的混洗数是卡特兰数 C(2n,n)/(n+1)
• ✓每个混洗唯一对应一个 push/pop 操作序列
• ✓可实现的混洗当且仅当不含 312 模式
• ✓判定方法：模拟入栈出栈，贪心匹配
• ✓栈混洗与合法括号序列本质同源

先自己想一会儿，再对照参考答案——答案只给路径，不给终点。