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

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

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

3、q2里面（所有元素的順序不會(huì)變化），直到剩下一個(gè)，再讓它出隊(duì)即可,6/21,例2 續(xù),入“?！保壕S護(hù)一個(gè)隊(duì)列是空的 : O(1) push(x) ： if (!q1.empty() q1.push(x); else q2.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ì)直接

4、入到s1里 要出隊(duì)如果s2非空，則先從s2出，否則把s1里面全部元素壓入s2中 理解： s1負(fù)責(zé)存放入隊(duì)元素 s2負(fù)責(zé)出隊(duì)并反向 每個(gè)元素實(shí)際上反向了兩次，出入一次s1,出入一次s2,8/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（笨）

5、用兩個(gè)堆棧，s1和s2，s1正常使用, s2一直是空的 getMin的時(shí)候，把s1的元素一個(gè)一個(gè)彈出到s2，每彈出一個(gè)，順便求當(dāng)前的最小值，然后再?gòu)膕2把元素一個(gè)一個(gè)彈回到s1，也清空了s2: O(n),10/21,例4 續(xù)1,方法2 用兩個(gè)堆棧，s1維護(hù)原來(lái)的值，s2維護(hù)最小值 它們?cè)貍€(gè)數(shù)一樣多 push(x): O(1) s1.push(x); if (!s2.empty() ,11/21,例4 續(xù)2,方法3 思路不變， s2真的需要存儲(chǔ)那么多值么？ 假設(shè)之前入過(guò)一個(gè)最小值，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 給出一個(gè)直方圖，求最大面積矩形 （Leetcode 84) 用堆棧計(jì)算每一塊板能延伸到的左右邊界 對(duì)每一塊板 堆棧頂矮，這一塊左邊界確定，入棧 堆棧頂高，堆棧頂右邊界確定，出棧，計(jì)算面積 入棧時(shí)左邊界確定 出棧時(shí)右邊界確定 堆棧里元素是遞增的 本質(zhì)：中間的短板沒(méi)有用！ 復(fù)雜度 O(n),13/21,例5 續(xù)1,14/21,例5 續(xù)2,15/21,例6 滑動(dòng)窗口最大值,給定一個(gè)數(shù)組a0.n,還有一

7、個(gè)值k，計(jì)算數(shù)組bi = max(ai k + 1. i) 注意認(rèn)為負(fù)數(shù)下標(biāo)對(duì)應(yīng)值是無(wú)窮小 方法1: 用一個(gè)最大堆存放最近的k個(gè)數(shù) 計(jì)算好bi 1后 ai k出堆， 如何找到ai k? ai入堆 bi = 堆頂 時(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先離開(kāi)窗口 y進(jìn)入窗口后x與y總是同時(shí)存在，直到x離開(kāi) x沒(méi)用了 利用這個(gè)性質(zhì)？ 雙端隊(duì)列，隊(duì)頭存舊的數(shù)，隊(duì)尾存新的數(shù) 如果隊(duì)尾的數(shù)將要入隊(duì)的數(shù)ai，則扔掉隊(duì)尾的數(shù) 隊(duì)列里的從隊(duì)頭到隊(duì)尾是單減的，隊(duì)頭永遠(yuǎn)是窗口最大值 考慮： 隊(duì)頭何時(shí)過(guò)期？ 時(shí)間復(fù)雜度？ O(n) :每個(gè)元素出入隊(duì)一次,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)椤斑^(guò)期”而“不得不”出隊(duì) 存放a數(shù)組的“下標(biāo)”而沒(méi)存放具體值 擴(kuò)展 如果輸入是一個(gè)流，我們必須自己保存“時(shí)間戳”，決定過(guò)期。,19/21,總結(jié),理解隊(duì)列堆棧的基本概念 n個(gè)左右括號(hào)的出入棧順序有多少種？（Catal