單調(diào)棧和單調(diào)隊(duì)列精品

1、單調(diào)棧和單調(diào)隊(duì)列by tisuama 定義： 單調(diào)棧：棧內(nèi)的元素，按照某種方式排序下（單調(diào)遞增或者單調(diào)遞減） 如果新入棧的元素破壞了單調(diào)性，就彈出棧內(nèi)元素，直到滿足單調(diào)性為什么要學(xué)習(xí)單調(diào)棧： 它可以很方便地求出某個(gè)數(shù)的左邊或者右邊第一個(gè)比它大或者小的元素，而且總時(shí)間復(fù)雜度o(n)。如何維護(hù)單調(diào)棧：（以維護(hù)單調(diào)遞增棧為例）進(jìn)棧操作：每次入棧前先檢驗(yàn)棧頂元素和進(jìn)棧元素(x)的大小，如果小于x，就讓x直接入棧。如果棧頂元素大于等于x,那么出棧，直到棧空或者棧頂元素小于x例如：1 4 3 6 0初始時(shí)刻?？眨?入棧。-棧內(nèi)元素(1)4要進(jìn)棧，4大于1，所以直接進(jìn)棧.-棧內(nèi)元素(1,4)3要進(jìn)棧，3小于

2、4,4出棧，3進(jìn)棧.-棧內(nèi)元素(1 3)6要進(jìn)棧，6大于3,6直接進(jìn)棧。-棧內(nèi)元素(1,3,6)0要入棧，1,3,6都出棧，-棧內(nèi)元素(0)例題poj 2559題意：給出一個(gè)柱形統(tǒng)計(jì)圖(histogram), 它的每個(gè)項(xiàng)目的寬度是1， 高度和具體問(wèn)題有關(guān)。 現(xiàn)在編程求出在這個(gè)柱形圖中的最大面積的長(zhǎng)方形（n=1e5)例如：2, 1, 4, 5, 1, 3, 3最大面積：8那么問(wèn)題來(lái)了：如何算？分析 逐個(gè)考慮每個(gè)項(xiàng)目，那么如何得到每個(gè)項(xiàng)目被包含的長(zhǎng)方形了？ 假設(shè)考慮到項(xiàng)目x,通過(guò)簡(jiǎn)單的思考，我們可以得出結(jié)論，x的左右兩邊的項(xiàng)目高度都不能比x低，那么如何求項(xiàng)目x的兩邊延伸長(zhǎng)度？ 我們想到了單調(diào)棧 ?

3、為什么 （以求x左邊延伸長(zhǎng)度為例）假設(shè)我們建立一個(gè)單調(diào)遞增棧,那么我們可以輕松地求得x左邊比x小的第一個(gè)數(shù)的位置。那么問(wèn)題來(lái)了：為什么是單調(diào)遞增棧，為什么是比x小？ 求x右邊延伸相同處理實(shí)現(xiàn)方式 棧（以求x的向左延伸為例） int top=0,smaxn; for(int i=1;i=hi) -top;li=(top=0?1:stop+1);s+top=i; 并查集l1=1;for(inti=2;i=1&hi=hpos-1) pos=lpos-1; li=pos;定義： 單調(diào)隊(duì)列：隊(duì)列中元素之間的關(guān)系具有單調(diào)性，而且，隊(duì)首和隊(duì)尾都可以進(jìn)行出隊(duì)操作，只有隊(duì)尾可以進(jìn)行入隊(duì)操作。為什么要學(xué)習(xí)

4、單調(diào)隊(duì)列： 對(duì)于維護(hù)好的單調(diào)隊(duì)列，對(duì)內(nèi)元素是有序的，那么取出最大值（最小值）的復(fù)雜度是o(1) 可以拿來(lái)優(yōu)化dp（然而弱不會(huì)）如何維護(hù)單調(diào)隊(duì)列：隊(duì)尾入隊(duì)的時(shí)候維護(hù)單調(diào)性。例題poj 2823給定一個(gè)大小已知的數(shù)組以及一個(gè)大小已知的滑動(dòng)窗口，窗口每個(gè)時(shí)刻向后移動(dòng)一位，求出每個(gè)時(shí)刻窗口中數(shù)字的最大值和最小值。(n=1e6)例如： input8 31 3 -1 -3 5 3 6 7output：-1 -3 -3 -3 3 33 3 5 5 6 7如何解啊如何解？區(qū)間最值問(wèn)題：我們想到了啥？線段樹(shù)？rmq？新姿勢(shì)！單調(diào)隊(duì)列！o(n)!o(nlog(n)!分析以得到最小值為例： 我們維護(hù)一個(gè)單增的隊(duì)列，

5、那么每次滑動(dòng)窗口入隊(duì)之后就要得到一個(gè)區(qū)間最小值，按照剛才的理論，直接取隊(duì)首元素就可以了？ 具體做法：每次滑動(dòng)窗口要得到最小值的時(shí)候，判斷隊(duì)首元素是否過(guò)期，如果過(guò)期，就從隊(duì)首出隊(duì)，繼續(xù)找。最大值做法同上：維護(hù)一個(gè)單減隊(duì)列。實(shí)現(xiàn)方式void get_min() int tail=0,head=1; for(int i=1;ik;i+) while(head=ai) -tail; q+tail=ai; ptail=i; for(int i=k;i=n;i+) while(head=ai) -tail; q+tail=ai; ptail=i; while(phead注意對(duì)象是隊(duì)內(nèi)元素，但是隊(duì)內(nèi)元素都是按次序入隊(duì)，即隊(duì)內(nèi)元素都是比當(dāng)前要