以求最大值為例

使用單調(diào)隊(duì)列儲(chǔ)存當(dāng)前窗口內(nèi)單調(diào)遞減的元素的下標(biāo)，隊(duì)首代表窗口內(nèi)的最大值元素，隊(duì)尾代表窗口內(nèi)的尾元素

也就是說(shuō)該單調(diào)隊(duì)列代表滑動(dòng)窗口內(nèi)的一個(gè)從最大值元素到尾元素降序子序列

隊(duì)列中需要存放窗口元素的下標(biāo)值，便于判斷隊(duì)首是否需要出隊(duì)（下面會(huì)解釋?zhuān)?/p>

一.隊(duì)列維護(hù)過(guò)程：

當(dāng)窗口發(fā)生滑動(dòng)時(shí)：先操作隊(duì)首，再操作隊(duì)尾

Ⅰ隊(duì)首：

只有當(dāng) 隊(duì)首的元素（窗口在未滑動(dòng)之前的最大值）從窗口滑出時(shí)，隊(duì)首進(jìn)行出隊(duì)操作pop_front

Ⅱ隊(duì)尾：

當(dāng)新元素滑入窗口時(shí)，需要把新元素插入隊(duì)尾，將會(huì)有兩種情況

1：直接插入：

當(dāng)新元素小于隊(duì)尾時(shí)（自然也小于隊(duì)列中所有元素），它可能在將來(lái)的某個(gè)時(shí)候成為隊(duì)首成為窗口的最大值，此時(shí)進(jìn)行入隊(duì)操作push_back

2：先刪后插：

當(dāng)新元素大于等于隊(duì)尾時(shí)，此時(shí)原隊(duì)尾永遠(yuǎn)不可能成為最大值，被舍棄刪除，進(jìn)行原隊(duì)尾出隊(duì)操作pop_back

重復(fù)此操作直到新元素小于隊(duì)尾或者隊(duì)列為空（說(shuō)明新元素是窗口滑動(dòng)后的最大值自然就把原隊(duì)列刪完了）

最后進(jìn)行新元素入隊(duì)push_back

這樣經(jīng)過(guò)一輪維護(hù)后得到的隊(duì)列就是一個(gè)單調(diào)遞減的隊(duì)列，隊(duì)首代表當(dāng)前窗口的最大值

二.樣例模擬：

數(shù)組：1 3 -1 -3 5 3 6 7

1：1 3 -1 -3 5 3 6 7

當(dāng)前隊(duì)列為空,1入隊(duì)

操作后隊(duì)列為：1

2：1 3 -1 -3 5 3 6 7

3!<1,1出隊(duì)

隊(duì)列空,3入隊(duì)

操作后隊(duì)列為：3

3：1 3 -1 -3 5 3 6 7

-1<3,-1入隊(duì)

操作后隊(duì)列為：3 -1

4：1 3 -1 -3 5 3 6 7

隊(duì)首未滑出

新元素-3<-1,-3入隊(duì)

操作后隊(duì)列為：3 -1 -3

5：1 3 -1 -3 5 3 6 7

隊(duì)首滑出，3出隊(duì)

新元素5!<-3,-3出隊(duì)

新元素5!<-1,-1出隊(duì)

隊(duì)列空，5入隊(duì)

操作后隊(duì)列：5

6：1 3 -1 -3 5 3 6 7

隊(duì)首未滑出

新元素3<5,3入隊(duì)

操作后隊(duì)列：5 3

7：1 3 -1 -3 5 3 6 7

隊(duì)首未滑出

新元素6!<3,3出隊(duì)

新元素6!<5,5出隊(duì)

隊(duì)列空,6入隊(duì)

操作后隊(duì)列：6

8：1 3 -1 -3 5 3 6 7

隊(duì)首未滑出

新元素7!<6,6出隊(duì)

隊(duì)列空,7入隊(duì)

操作后隊(duì)列：7

得出答案：3 3 5 5 6 7

三.代碼：

如何判斷隊(duì)首元素是否從窗口中滑出？

如果用數(shù)組中元素的值，不易判斷

如果隊(duì)列中儲(chǔ)存的是數(shù)組元素的下標(biāo)，可以通過(guò)窗口循環(huán)變量i和隊(duì)首所代表的下標(biāo)作差，看是否超過(guò)窗口長(zhǎng)度

窗口最右端下標(biāo)：循環(huán)變量i

窗口最左端下標(biāo)：i-len+1