序列元素IT面試題——判斷合法出棧序列

本文純屬個人見解，是對前面學習的總結，如有描述不正確的地方還請高手指正~

????在技巧筆試口試上，我們常常會碰到這樣一類題型，如給你一個入棧序列，然后再讓你判斷幾個序列是否有可能為它的出棧序列，如：

????入棧序列為 1 2 3 4 5，則 1 2 3 4 5可能為它的出棧序列，而 5 4 1 2 3弗成能為它的出棧序列。

????對于n比較小的情況，我們往往可以通過手動模擬的方法來判斷，對于n比較大的時候，這種方法就顯得效率不佳了。

????下面分析一種通用的方法判斷正當出棧序列，時間復雜度為O(n)。為了敘說便利，我們不妨設入棧序列為 1 2 3.......n，并且每一個元素各不相等。

????事實上，一個出棧序列固定的話，那么沒個數的出棧順序和時間都是固定的，則我們可以模擬棧的入棧出棧過程，來判斷是否一個正當的出棧序列。

????我們首先設po為目前為止入棧的元素中最大的數，初始化為0，若下一個出棧元素要大于po的話（設為x），說明我必須將[po+1,x]中的全部書都入棧，再將x彈出便可（這時還應把po賦值為x）。否則說明下一個出棧的元素已經在棧中，并且肯定是棧頂元素，若棧頂元素與下一個出棧元素不相等的話，我們可以判斷這不是一個正當出棧序列，否則，若全部的出棧元素都不引起沖突，則說明這是一個正當序列。這里再說一下時間復雜度，因為我們只有在下一個出棧元素大于po時，才將元素壓入棧中，并且我們每一次判斷一個出棧元素是否發生沖突時，都會將棧頂元素彈出，所以每一個元素都入棧一次，出棧一次，所以時間復雜度為O(n)。

每日一道理
燈，帶有一種明亮的光，每當深夜來臨，是它陪伴著你，如此默默無聞。它是平凡的，外表華麗與否，那都是一樣的，珍珠點綴，水晶加飾的燈它只能用以裝飾，來滿足人們的虛榮心，比起這，普普通通的日光燈是幸運的，因為它照明的本性沒有改變，如同生活中的一部分人平平凡凡卻實實在在。

????算法的具體實現請看代碼。

????

????代碼如下：

#include <stdio.h>
#define maxn 1005
int stack[maxn],top;
int out[maxn];
int check(int n)
{int po=0;for(int i=1;i<=n;i++){for(int j=po+1;j<=out[i];j++){po=j;stack[top++]=j;}if(stack[--top]!=out[i])return 0;}return 1;
}
int main()
{int n;scanf("%d",&n);//假設入棧序列為1 2。。。。nfor(int i=1;i<=n;i++){scanf("%d",&out[i]);}if(check(n))printf("Yes\n");elseprintf("No\n");return 0;
}

????

文章結束給大家分享下程序員的一些笑話語錄： 3G普不普及現在已經不是看終端了，而是看應用，有好的，便宜實用的應用，花1000多買個能用的智能手機應該不是什么難事。反過來說，你200元拿一個智能手機，沒有好的應用，看個電影要幾十元，也是沒人用3G。