前言：如果我們嘗試在網(wǎng)上搜索這個(gè)問(wèn)題的話，大部分的搜索結(jié)果都會(huì)提到卡塔蘭數(shù)，這個(gè)算法的思路在筆者看來(lái)十分新穎有趣，并且其計(jì)算方式極其簡(jiǎn)單，在此記錄下。

棧的定義：

????????首先讓我們來(lái)了解/回顧一下“?！边@種數(shù)據(jù)結(jié)構(gòu)。嚴(yán)謹(jǐn)?shù)亩x是棧（stack）是只允許在一端進(jìn)行插入或刪除操作的線性表。而形象的理解就是有一個(gè)狹窄的單開(kāi)口盒子，后進(jìn)入的元素會(huì)“阻塞”這個(gè)盒子，所以我們每次只能從這個(gè)盒子的最上面（棧頂）取出元素。因?yàn)樽铐斏系囊欢ㄊ亲詈竺娣胚M(jìn)去的，因此棧有后入先出的特點(diǎn)。

出棧順序：

????????讓我們回到這個(gè)經(jīng)典問(wèn)題“N個(gè)數(shù)依次入棧，出棧順序有多少種？”，由于題目只限制了依次入棧，并沒(méi)有限制一定要全部入棧才可以出棧，因此會(huì)有多種不同的出棧順序。如對(duì)于依次入棧的a, b, c三個(gè)元素，我們可以先全部入棧再依次出棧，這樣的結(jié)果就是c, b, a。當(dāng)然我們也可以選擇先入棧a，然后立即出棧a，再入棧b，出棧b，以此類(lèi)推，因此這種情況下的結(jié)果就是a, b, c。有興趣的讀者可以繼續(xù)推導(dǎo)下其他可能性，總共是有5種不同的排列。那么這個(gè)5是如何得出來(lái)的呢？下面就進(jìn)入到本篇文章的正題了。

有趣的算法：

????????首先我們從整體看棧的行為，有入棧就必定有出棧，即如果把入棧和出棧看作一種行為的話，對(duì)于N個(gè)數(shù)來(lái)說(shuō)，存在著2N個(gè)行為。

????????我們把入棧記錄為1，出棧記錄為0，則尋找出棧順序種類(lèi)的問(wèn)題轉(zhuǎn)化為了尋找有效的2N數(shù)字排序。

????????我們先不論該序列是否有效：對(duì)于N個(gè)1與N個(gè)0的排序，很簡(jiǎn)單有C(2n,n)種。

????????然后我們討論什么是有效：很顯然，必須先有入棧才能有出棧，即從頭開(kāi)始的任意長(zhǎng)序列中1的數(shù)量必定比0多。我們既然已經(jīng)知道了任意排列的總數(shù)，那么只需要找到無(wú)效序列數(shù)量，將其減去即可。而對(duì)于某個(gè)無(wú)效序列，必定存在某一2m+1長(zhǎng)度中，存在m個(gè)1，m+1個(gè)0（即出棧次數(shù)大于入棧次數(shù)）。這時(shí)我們截取這一長(zhǎng)度序列作為左序列，而右序列剩下的數(shù)字中顯然1比0多一位。于是我們將右序列中的1與0互換，與左序列拼合，則這一新序列由n+1個(gè)0與n-1個(gè)1組成，即存在該無(wú)效序列對(duì)于新序列的某種映射關(guān)系，并且該關(guān)系對(duì)任意一個(gè)無(wú)效序列均成立。

????????然后我們來(lái)分析下新序列：對(duì)于任意n+1個(gè)0與n-1個(gè)1組成的序列，由于0的個(gè)數(shù)多2個(gè)，2n為偶數(shù)，故必在某一個(gè)奇數(shù)位上出現(xiàn)0的累計(jì)數(shù)超過(guò)1的累計(jì)數(shù)，也即總是存在某一2m+1長(zhǎng)度上，存在m個(gè)1，m+1個(gè)0。我們截取這一長(zhǎng)度序列作為左序列，顯然它與無(wú)效序列的左序列是完全一致的。我們觀察剩下的數(shù)字，其中0的數(shù)量比1的多一個(gè)，也即無(wú)效序列的右部分處理后的狀態(tài)。于是我們得出無(wú)效序列與新序列存在一一映射關(guān)系，也即求無(wú)效序列的種類(lèi)數(shù)量就轉(zhuǎn)變成了求新序列的種類(lèi)數(shù)量。顯然新序列的數(shù)量就是簡(jiǎn)單的組合數(shù) C(2n,n+1)

????????這樣我們就得到了最終的結(jié)果 輸出序列的總數(shù)目=C(2n,n)-C(2n,n+1)=C(2n,n)/(n+1)

????????Q：如何證明這兩種序列是一一對(duì)應(yīng)的？

????????A：假設(shè)非法序列為 A，對(duì)應(yīng)的序列為 B。對(duì)于任意一個(gè)A，總能通過(guò)上述的映射關(guān)系找到唯一的B，同樣的，對(duì)于任意一個(gè)B，有且僅有一個(gè)A與之對(duì)應(yīng)，這樣就可以說(shuō)他們是一一對(duì)應(yīng)的映射關(guān)系。

參考網(wǎng)址：

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

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