棧和隊(duì)列高頻面試題精講-七月算法出品

棧和隊(duì)列面試題精講

七月算法

曹鵬

2015年4月23日2/21提綱線性表簡介面試題總體分析一些例題例1元素出入棧順序合法性判斷例2用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)堆棧例3用兩個(gè)堆棧實(shí)現(xiàn)一個(gè)隊(duì)列例4支持查詢最小值的堆棧例5單調(diào)堆?！畲笾狈綀D例6單調(diào)隊(duì)列——滑動(dòng)窗口最大值總結(jié)線性表簡介堆棧和隊(duì)列統(tǒng)稱線性表簡單的線性結(jié)構(gòu)數(shù)組和鏈表可以實(shí)現(xiàn)這兩種數(shù)據(jù)結(jié)構(gòu)堆棧后進(jìn)先出(LastInFirstOut)隊(duì)列先進(jìn)先出(FirstInFirstOut)3/21面試題總體分析堆棧基本理解DFS深度優(yōu)先——按深度遍歷遞歸轉(zhuǎn)非遞歸隊(duì)列基本理解BFS廣度優(yōu)先——按層序遍歷4/21例1元素出入棧順序合法性判斷例1給定一些元素的入棧順序和出棧順序，問是否可能？（假設(shè)所有元素都不相同）分析：

模擬堆棧即可，如果當(dāng)前要出棧的元素恰好在棧頂，則必須出棧，否則就入棧。（注意判斷兩個(gè)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用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)堆棧例2如何用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)堆棧？隊(duì)列無論怎么折騰，元素順序不會(huì)改變！

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

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

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

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

它們元素個(gè)數(shù)一樣多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續(xù)2方法3思路不變，s2真的需要存儲(chǔ)那么多值么？

假設(shè)之前入過一個(gè)最小值，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給出一個(gè)直方圖，求最大面積矩形

（Leetcode84)用堆棧計(jì)算每一塊板能延伸到的左右邊界對每一塊板堆棧頂矮，這一塊左邊界確定，入棧堆棧頂高，堆棧頂右邊界確定，出棧，計(jì)算面積入棧時(shí)左邊界確定出棧時(shí)右邊界確定堆棧里元素是遞增的本質(zhì)：中間的短板沒有用！復(fù)雜度O(n)13/21例5續(xù)114/21H0123456值2156230新數(shù)堆棧(頂->底)說明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

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

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

續(xù)3實(shí)現(xiàn)：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();//扔隊(duì)尾q.push(i);//入隊(duì)b[i]=a[q.front()];}理解：舊的數(shù)比較大，因?yàn)椤斑^期”而“不得不”出隊(duì)存放a數(shù)組的“下標(biāo)”而沒存放具體值擴(kuò)展如果輸入是一個(gè)流，我們必須自己保存“時(shí)間戳