有一個(gè)火車(chē)站，鐵路如圖所示，每輛火車(chē)從A駛?cè)耄購(gòu)腂方向駛出，同時(shí)它的車(chē)廂可以重新組合。假設(shè)從A方向駛來(lái)的火車(chē)有n節(jié)（n≤1000），分別按照順序編號(hào)為1，2，3，…，n。假定在進(jìn)入車(chē)站前，每節(jié)車(chē)廂之間都不是連著的，并且它們可以自行移動(dòng)到B處的鐵軌上。另外假定車(chē)站C可以停放任意多節(jié)車(chē)廂。但是一旦進(jìn)入車(chē)站C，它就不能再回到A方向的鐵軌上了，并且一旦當(dāng)它進(jìn)入B方向的鐵軌，它就不能再回到車(chē)站C

負(fù)責(zé)車(chē)廂調(diào)度的工作人員需要知道能否使它以a1,a2,…,an的順序從B方向駛出，請(qǐng)來(lái)判斷能否得到指定的車(chē)廂順序。

5
5 4 3 2 1

YES

解析：觀察發(fā)現(xiàn)，整個(gè)調(diào)度過(guò)程其實(shí)是在模擬入棧出棧的過(guò)程，而這個(gè)過(guò)程中，我們可以分成三種狀態(tài)：棧前、棧中、棧后。我們可以發(fā)現(xiàn)，當(dāng)某個(gè)數(shù)字出棧了，說(shuō)明比它小的數(shù)字要么已經(jīng)出棧了，要么還在棧里，不能是入棧前狀態(tài)，并且在棧中的順序是從大到小的(從棧頂往棧底看)，比如出5，那么1，2，3，4要么已經(jīng)在5之前出了，要么還在棧中（假如1，3，4在棧中，從棧頂往棧底看依次為4，3，1），不能是入棧前的狀態(tài)。如果某個(gè)數(shù)字要出棧，那么當(dāng)前在棧中的數(shù)字都必須小于它，否則就與棧的性質(zhì)矛盾，不合法，于是我們可以這樣解決：

從第一個(gè)數(shù)字開(kāi)始掃描，a[i]表示當(dāng)前出棧的數(shù)字，如果有比a[i]大的數(shù)字還在棧中，那么就產(chǎn)生矛盾，輸出“NO”；否則，標(biāo)記當(dāng)前數(shù)字a[i]為棧后狀態(tài)，那么[1, a[i]-1]這些數(shù)字如果還沒(méi)出棧，標(biāo)記為棧中狀態(tài)。具體我們可以用0表示為確定狀態(tài)，1表示棧中狀態(tài)，2表示棧后狀態(tài)。