【面試試題】3棧和隊列面試題精講

1、棧和隊列面試題精講,七月算法 曹鵬 2015年4月23日,2/21,提綱,線性表簡介 面試題總體分析 一些例題 例1 元素出入棧順序合法性判斷 例2 用兩個隊列實(shí)現(xiàn)一個堆棧 例3 用兩個堆棧實(shí)現(xiàn)一個隊列 例4 支持查詢最小值的堆棧 例5 單調(diào)堆棧最大直方圖 例6 單調(diào)隊列滑動窗口最大值 總結(jié),線性表簡介,堆棧和隊列統(tǒng)稱線性表 簡單的線性結(jié)構(gòu) 數(shù)組和鏈表可以實(shí)現(xiàn)這兩種數(shù)據(jù)結(jié)構(gòu) 堆棧 后進(jìn)先出 (Last In First Out) 隊列 先進(jìn)先出 (First In First Out),3/21,面試題總體分析,堆棧 基本理解 DFS 深度優(yōu)先按深度遍歷 遞歸轉(zhuǎn)非遞歸 隊列 基本理解 BFS

2、廣度優(yōu)先按層序遍歷,4/21,例1 元素出入棧順序合法性判斷,例1 給定一些元素的入棧順序和出棧順序，問是否可能？（假設(shè)所有元素都不相同） 分析： 模擬堆棧即可，如果當(dāng)前要出棧的元素恰好在棧頂，則必須出棧，否則就入棧。（注意判斷兩個vector size一樣) bool isPossible(vector ,5/21,例2 用兩個隊列實(shí)現(xiàn)一個堆棧,例2 如何用兩個隊列實(shí)現(xiàn)一個堆棧？ 隊列無論怎么折騰，元素順序不會改變！ 兩個隊列來回倒，保證一個隊列是空的，用空隊列臨時存儲除隊尾外所有元素 例如 q1非空，q2是空的，要出“棧”，實(shí)際上要出的是q1里面最后一個元素，我們把q1里面元素一個一個放入

3、q2里面（所有元素的順序不會變化），直到剩下一個，再讓它出隊即可,6/21,例2 續(xù),入“棧”：維護(hù)一個隊列是空的 : O(1) push(x) ： if (!q1.empty() q1.push(x); else q2.push(x); 出“?！保河靡粋€隊列臨時存放元素 : O(n) pop() ： if (!q1.empty() while (q1.size() 1) q2.push(q1.front(); q1.pop(); q1.pop(); else /類似操作,7/21,例3 用兩個堆棧實(shí)現(xiàn)一個隊列,例3 如何堆棧實(shí)現(xiàn)一個隊列？ s1負(fù)責(zé)“入隊”，s2負(fù)責(zé)“出隊”（反向） 入隊直接

4、入到s1里 要出隊如果s2非空，則先從s2出，否則把s1里面全部元素壓入s2中 理解： s1負(fù)責(zé)存放入隊元素 s2負(fù)責(zé)出隊并反向 每個元素實(shí)際上反向了兩次，出入一次s1,出入一次s2,8/21,例3 續(xù),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得到當(dāng)前堆棧里所有元素的最小值 方法1（笨）

5、用兩個堆棧，s1和s2，s1正常使用, s2一直是空的 getMin的時候，把s1的元素一個一個彈出到s2，每彈出一個，順便求當(dāng)前的最小值，然后再從s2把元素一個一個彈回到s1，也清空了s2: O(n),10/21,例4 續(xù)1,方法2 用兩個堆棧，s1維護(hù)原來的值，s2維護(hù)最小值 它們元素個數(shù)一樣多 push(x): O(1) s1.push(x); if (!s2.empty() ,11/21,例4 續(xù)2,方法3 思路不變， s2真的需要存儲那么多值么？ 假設(shè)之前入過一個最小值，s2的頂端存了許多相同的最小值 push(x): O(1) s1.push(x); if (s2.empty()

6、| s2.top() = x) s2.push(x); pop : O(1) if (s1.top() = s2.top() s2.pop(); s1.pop();,12/21,例5 最大直方圖,例5 給出一個直方圖，求最大面積矩形 （Leetcode 84) 用堆棧計算每一塊板能延伸到的左右邊界 對每一塊板 堆棧頂矮，這一塊左邊界確定，入棧 堆棧頂高，堆棧頂右邊界確定，出棧，計算面積 入棧時左邊界確定 出棧時右邊界確定 堆棧里元素是遞增的 本質(zhì)：中間的短板沒有用！ 復(fù)雜度 O(n),13/21,例5 續(xù)1,14/21,例5 續(xù)2,15/21,例6 滑動窗口最大值,給定一個數(shù)組a0.n,還有一

7、個值k，計算數(shù)組bi = max(ai k + 1. i) 注意認(rèn)為負(fù)數(shù)下標(biāo)對應(yīng)值是無窮小 方法1: 用一個最大堆存放最近的k個數(shù) 計算好bi 1后 ai k出堆， 如何找到ai k? ai入堆 bi = 堆頂 時間復(fù)雜度O(nlogk),16/21,例6 續(xù)1,方法2 如果同時存在一個舊的數(shù)x,和一個新的數(shù)y并且x y，則x永遠(yuǎn)不會是我們要的解。因?yàn)椋?“窗口”朝右滑動 x先離開窗口 y進(jìn)入窗口后x與y總是同時存在，直到x離開 x沒用了 利用這個性質(zhì)？ 雙端隊列，隊頭存舊的數(shù)，隊尾存新的數(shù) 如果隊尾的數(shù)將要入隊的數(shù)ai，則扔掉隊尾的數(shù) 隊列里的從隊頭到隊尾是單減的，隊頭永遠(yuǎn)是窗口最大值 考慮： 隊頭何時過期？ 時間復(fù)雜度？ O(n) :每個元素出入隊一次,17/21,例6 續(xù)2,K = 3,18/21,例6 續(xù)3,實(shí)現(xiàn)： for (int i = 0; i n; +i) while (!q.empty() 理解： 舊的數(shù)比較大，因?yàn)椤斑^期”而“不得不”出隊 存放a數(shù)組的“下標(biāo)”而沒存放具體值 擴(kuò)展 如果輸入是一個流，我們必須自己保存“時間戳”，決定過期。,19/21,總結(jié),理解隊列堆棧的基本概念 n個左右括號的出入棧順序有多少種？（Catal