Henry Z's blog
面试算法题 - 出栈次序问题 (Catalan Number)
之前去方付通面试的时候的时候, 问了我N个数依次入栈，出栈顺序有多少种？的算法题, 其实是卡特兰数(Catalan)的应用.
当时没有答出来(这要是之前没有接触过, 谁答的出来).
现在用这篇日志重新整理记录一下.
问题的定义
一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列?
解题思路
- 假设进栈序列为[1, 2, 3, 4, 5, 6]
- 因为每个数字都可能是最后一个出栈的(独立的事件), 所以先单独分析当k为最后一个出栈数字的情况.
- 当
k进栈时, [1, 2]肯定已经出栈了, 所以他们([1, 2])的出栈序列总数为f(k-1)
- 当
- 当
k出栈时, 因为3为最后一个出栈, [4, 5, 6]肯定也已经出栈了, 所以他们[4, 5, 6]的出栈序列总数为f(n-k)
- 所以当k为出栈序列的最后一个数字时, 可能序列的总和为
f(k-1)*f(n-k) - 又因为第二条中, 每个事件为独立的, 所以最后得到了这么一个推导式:
f(0) = f(1) = 1f(n) = f(0)*f(n-1)+f(1)*f(n-2) + ... + f(n-1)*f(0) (n>=2)