棧和隊列面試題精講

七月算法

曹鵬

2015年4月23日2/21提綱線性表簡介面試題總體分析一些例題例1元素出入棧順序合法性判斷例2用兩個隊列實現一個堆棧例3用兩個堆棧實現一個隊列例4支持查詢最小值的堆棧例5單調堆棧——最大直方圖例6單調隊列——滑動窗口最大值總結線性表簡介堆棧和隊列統稱線性表簡單的線性結構數組和鏈表可以實現這兩種數據結構堆棧后進先出(LastInFirstOut)隊列先進先出(FirstInFirstOut)3/21面試題總體分析堆棧基本理解DFS深度優先——按深度遍歷遞歸轉非遞歸隊列基本理解BFS廣度優先——按層序遍歷4/21例1元素出入棧順序合法性判斷例1給定一些元素的入棧順序和出棧順序，問是否可能？（假設所有元素都不相同）分析：

模擬堆棧即可，如果當前要出棧的元素恰好在棧頂，則必須出棧，否則就入棧。（注意判斷兩個vectorsize一樣)boolisPossible(vector<int>&in,vector<int>&out){ for(inti=0,j=0;j<out.size();++j){ while(s.empty()||s.top()!=out[j]){ if(i>=in.size())returnfalse; s.push(in[i++]); } s.pop();}returntrue;}

5/21例2用兩個隊列實現一個堆棧例2如何用兩個隊列實現一個堆棧？隊列無論怎么折騰，元素順序不會改變！

兩個隊列來回倒，保證一個隊列是空的，用空隊列臨時存儲除隊尾外所有元素例如q1非空，q2是空的，要出“棧”，實際上要出的是q1里面最后一個元素，我們把q1里面元素一個一個放入q2里面（所有元素的順序不會變化），直到剩下一個，再讓它出隊即可6/21例2續入“棧”：維護一個隊列是空的:O(1)push(x)：if(!q1.empty())q1.push(x);elseq2.push(x);

出“棧”：用一個隊列臨時存放元素:O(n)pop()： if(!q1.empty()){ while(q1.size()>1){q2.push(q1.front());q1.pop();}q1.pop(); }else{//類似操作}

7/21例3用兩個堆棧實現一個隊列例3如何堆棧實現一個隊列？s1負責“入隊”，s2負責“出隊”（反向）入隊直接入到s1里要出隊如果s2非空，則先從s2出，否則把s1里面全部元素壓入s2中理解：s1負責存放入隊元素s2負責出隊并反向每個元素實際上反向了兩次，出入一次s1,出入一次s28/21例3續push(x):O(1) s1.push(x)pop:均攤O(1)每個元素出入兩個棧各1次if(s2.empty()){while(!s1.empty()){s2.push(s1.top());s1.pop();} }s2.pop();

9/21例4支持查找最小元素的堆棧一個堆棧除了支持push,pop以外還要支持一個操作getMin得到當前堆棧里所有元素的最小值方法1（笨）用兩個堆棧，s1和s2，s1正常使用,s2一直是空的getMin的時候，把s1的元素一個一個彈出到s2，每彈出一個，順便求當前的最小值，然后再從s2把元素一個一個彈回到s1，也清空了s2:O(n)10/21例4續1方法2用兩個堆棧，s1維護原來的值，s2維護最小值

它們元素個數一樣多push(x):O(1)s1.push(x);if(!s2.empty()&&s2.top()<x)s2.push(s2.top());elses2.push(x);pop():O(1)s1.pop();s2.pop();getMin:O(1)returns2.top();11/21例4續2方法3思路不變，s2真的需要存儲那么多值么？

假設之前入過一個最小值，s2的頂端存了許多相同的最小值

push(x):O(1)s1.push(x);if(s2.empty()||s2.top()>=x)s2.push(x);pop:O(1)if(s1.top()==s2.top())s2.pop();s1.pop();12/21例5最大直方圖例5給出一個直方圖，求最大面積矩形

（Leetcode84)用堆棧計算每一塊板能延伸到的左右邊界對每一塊板堆棧頂矮，這一塊左邊界確定，入棧堆棧頂高，堆棧頂右邊界確定，出棧，計算面積入棧時左邊界確定出棧時右邊界確定堆棧里元素是遞增的本質：中間的短板沒有用！復雜度O(n)13/21例5續114/21H0123456值2156230新數堆棧(頂->底)說明H[0]=2{2}2入棧,左邊界(-1)H[1]=1{1}2出棧，右邊界（1），1入棧，左邊界(-1)

H[2]=5{5,1}5入棧

，左邊界（1）H[3]=6{6，5，1}6入棧，左邊界（2）H[4]=2{2,1}6，5出棧，右邊界（4），2入棧左邊界（1）H[5]=3{3,2,1}3入棧，左邊界(4)H[6]=03,2,1,出棧右邊界（6）例5

續215/21例6滑動窗口最大值給定一個數組a［0..n],還有一個值k，計算數組b［i］=max(a[i–k+1..i])注意認為負數下標對應值是無窮小方法1:用一個最大堆存放最近的k個數計算好b[i–1]后a[i–k]出堆，

如何找到a[i–k]?a[i]入堆b[i]=堆頂時間復雜度O(nlogk),16/21例6續1方法2如果同時存在一個舊的數x,和一個新的數y并且x≤y，則x永遠不會是我們要的解。因為：“窗口”朝右滑動x先離開窗口y進入窗口后x與y總是同時存在，直到x離開x沒用了……利用這個性質？雙端隊列，隊頭存舊的數，隊尾存新的數如果隊尾的數≤將要入隊的數a[i]，則扔掉隊尾的數隊列里的從隊頭到隊尾是單減的，隊頭永遠是窗口最大值考慮：隊頭何時過期？時間復雜度？O(n):每個元素出入隊一次17/21例6續2K=318/21a012345值513426新數隊列(頭->尾）說明a[0]=5{5}5入隊,b[0]=5a[1]=1{5,1}1比5小直接入隊,b[1]=5a[2]=3{5,3}1太小了,被扔掉，3入隊,b[2]=5a[3]=4{4}5過期了，被扔掉。3比4小，被扔掉,b[3]=4a[4]=2{4,2}2比4小，入隊,b[4]=4a[5]=6{6}6最大，把2和4都扔掉,b[5]=6例6

續3實現：for(inti=0;i<n;++i){ while(!q.empty()&&q.front()<=i–k)q.pop_front();//過期 while(!q.empty()&&a[q.back()]<=a[i])q.pop_back();//扔隊尾q.push(i);//入隊b[i]=a[q.front()];}理解：舊的數比較大，因為“過期”而“不得不”出隊存放a數組的“下標”而沒存放具體值擴展如果輸入是一個流，我們必須自己保存“時間戳