單調隊列是一種用來快速查詢一段長度為n的數(shù)組的一部分的最大最小值的算法。它原理相對簡單，且易于實現(xiàn)，并且時間復雜度是接近O(n)的，可以解決很多問題。下面以洛谷P1886滑動窗口 /【模板】單調隊列為例來介紹單調隊列的實現(xiàn)方法。

先放上題目：

題目描述

有一個長為n

例如：

The array is

輸入格式

輸入一共有兩行，第一行有兩個正整數(shù)

輸出格式

輸出共兩行，第一行為每次窗口滑動的最小值
第二行為每次窗口滑動的最大值

解法介紹：

單調隊列并不使用queue，而只需要在原序列中維護兩個邊界，分別為l和r，代表研究的部分的左邊界位置、右邊界位置。我們將左邊界的位置初始化為1，右邊界的位置初始化為k，代表最初這個研究部分只包含a[1]到a[k]這些節(jié)點。此時，我們并不知道這個子區(qū)間的最大值和最小值分別是多少，所以我們需要維護一個find函數(shù)來尋找子區(qū)間內的最大、最小值。這里我們進行一次find初始化，并且對最初的最大值、最小值進行記錄。find函數(shù)只需要從l到r進行枚舉查詢即可。

find函數(shù)代碼實現(xiàn)如下：

1 const int inf=0x3f3f3f3f;
2 void find(int l,int r){
3     maxn=-inf;minn=inf;//初始化最大值和最小值
4     for(int i=l;i<=r;i++){
5         maxn=max(maxn,a[i]);
6         minn=min(minn,a[i]);
7     }
8 }

接下來我們需要對這個窗口進行滑動操作。我們總共需要向右移動(n-k+1)次，每一次都要進行l(wèi)++，r++的操作。而在操作的時候我們需要維護最值，這也是最為重要的操作。

我們在維護時要分很多種情況：

第一種，也是最好處理的一種情況，當在進行l(wèi)++操作之前的l所對應的a[l]既不是上一個窗口所對應的最大值，又不是它所對應的最小值時，刪去這個值并不會影響窗口內的最大值和最小值，這時候我們可以放心的l++，r++，然后用新加入單調隊列的a[r]對maxn和minn進行update更新即可。

代碼：

 1 void update(){
 2   l++;
 3   r++;
 4   maxn=max(maxn,a[r]);
 5   minn=min(minn,a[r]);
 6 }
 7 //接下來是在循環(huán)中的判斷
 8 if(a[l]!=maxn&&a[l]!=minn){
 9   update();
10 }

第二種，當在進行l(wèi)++操作之前的l所對應的a[l]是上一個窗口所對應的最大值，而不是它所對應的最小值時，刪除a[l]會對新區(qū)間內的最大值造成影響，我們已經(jīng)不知道除了這個被刪除掉的節(jié)點以外，新窗口的最大值是多少，所以我們要重新查找。但是，這種情況不會對最小值造成影響。但是，如果新加入的節(jié)點要大于等于要刪除的節(jié)點，那么刪除掉這個節(jié)點也就無所謂了。所以我們還需要加入一個判斷：

1 if(a[l]==maxn){//如果左邊界的值等于最大值 
2     if(a[r+1]>=a[l]){//新加入節(jié)點值大于等于刪除的節(jié)點 
3         update();//不需要重新查找 
4     }else{
5         l++;
6         r++;
7         find(l,r);//否則重新查找 
8     }
9 }

第三種，當在進行l(wèi)++操作之前的l所對應的a[l]是上一個窗口所對應的最小值，而不是它所對應的最大值時，我們可以用與第二種情況相同的方式來查找。代碼如下：

1 if(a[l]==minn){ 
2   if(a[r+1]<a[l]){
3       update();
4   }else{
5       l++;
6       r++;
7       find(l,r);
8   }
9 }

第四種，也是最為玄學的一種情況，就是當在進行l(wèi)++操作之前的l所對應的a[l]既是上一個窗口所對應的最小值，又是它所對應的最大值的情況。這種情況下直接重新查找就可以了，畢竟這種情況極少，且考慮起來會很麻煩。

代碼：

1 if(a[l]==maxn&&a[l]==minn){
2     l++;
3     r++;
4     find(l,r);
5 }

最后附上完整代碼：

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 const int inf=0x3f3f3f3f;
 5 int n,k; 
 6 int l,r;
 7 int a[1000005];
 8 int maxn,minn;
 9 int max_ans[1000005],min_ans[1000005];
10 void record(int now){
11     max_ans[now]=maxn;
12     min_ans[now]=minn;
13 }
14 void find(int l,int r){
15     maxn=-inf;
16     minn=inf;
17     for(int i=l;i<=r;i++){
18         maxn=max(maxn,a[i]);
19         minn=min(minn,a[i]);
20     }
21 }
22 void update(){
23     l++;
24     r++;
25     maxn=max(a[r],maxn);
26     minn=min(a[r],minn);
27 }
28 int main(){
29     cin>>n>>k;
30     for(int i=1;i<=n;i++){
31         cin>>a[i];
32     }
33     l=1;
34     r=k;
35     find(l,r);
36     for(int i=1;i<=n-k+1;i++){
37         record(i);
38         if(a[l]!=maxn&&a[l]!=minn){
39             update();
40         }else if(a[l]==maxn&&a[l]==minn){
41             l++;
42             r++;
43             find(l,r);
44         }else if(a[l]==maxn){
45             if(a[r+1]>a[l]){
46                 update();
47             }else{
48                 l++;
49                 r++;
50                 find(l,r);
51             }
52         }else{
53             if(a[r+1]<a[l]){
54                 update();
55             }else{
56                 l++;
57                 r++;
58                 find(l,r);
59             }
60         }
61     }
62     for(int i=1;i<=n-k+1;i++){
63         cout<<min_ans[i]<<' ';
64     }
65     cout<<endl;
66     for(int i=1;i<=n-k+1;i++){
67         cout<<max_ans[i]<<' ';
68     }
69     cout<<endl;
70     return 0;
71 }

posted on 2020-10-15 17:32 郭謙閱讀(479) 評論(0) 收藏舉報

刷新頁面返回頂部

公告