單調隊列 —— 滑動窗口

2021 年 2 月 21 日
筆記
演算法

dequeue雙向隊列

dequeue<int>que;//創建雙向隊列
que.push_front()//在隊列前面塞一個元素
que.push_back()//在隊列後面塞一個元素
que.pop_front()//刪除隊列第一個元素
que.pop_back()//刪除隊列的最後一個元素
que.clear()//清空隊列
que.empty()//判斷是否為空
que.size()//返回隊列元素個數

單調隊列

問題：

對每個長度為k的滑動窗體，求其最大值和最小值

思路1:

使出秘技dequeue （STL賽高！）

這裡根據雨巨生動形象的例子，我來簡單描述一下下：

題意：給出各屆acmer的實力，眾所周知大學基本上是四年，所以我們滑動窗口的大小就是4，問每個窗口中實力最強與最弱的是多少

舉個樣例：1 4 6 3 3 3 2

我們現在先求最大值，最小值在最大值的基礎上改一改就行。

首先我們看給1入隊列（是dequeue，後面不贅述），因為沒到達四個元素，所以不輸出，再到第二個元素4，大於1，說明在4的偉大作用下，1已經廢了，就直接扔出去，也就是「去尾」，得到隊列 4 。再到6，6 > 4，所以在6的存在下，4 廢了，扔出去，得到隊列 6。再到3，3 小於6，說明他有機會，因為可以等到6的退役了（也就是6滑出窗口了），他就可能是最大的，把 3塞進去，得到6，3的隊列，現在達到窗口的大小，所以輸出隊頭6，再看3，等於隊列尾的元素，就把他也塞進去，再輸出一個6，下一個3塞進來以後，我們判斷發現隊列頭還沒有出窗口，就再輸出6，到了2，塞進去，發現6已經出了窗口，就得「去頭」，所以輸出3

總結一下，實現單調隊列，主要分四個部分：

去尾：隊尾元素出隊列。當有新的acmer等待入隊時，需要從隊尾開始判斷會不會破壞隊的單調性，會的話就去尾。
入隊：將新隊員從隊尾塞進來
去頭：隊頭元素出隊列。當acmer滿四年後就得退役，也就是要將其扔出隊列
取解：取隊頭元素

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 1000000 + 5
typedef  long long ll ;
inline int IntRead(){//int的快讀
    char ch = getchar();
    int s = 0, w = 1;
    while(ch < '0' || ch > '9'){
        if(ch == '-') w = -1;
        ch = getchar();}
    while(ch >= '0' && ch <= '9'){
        s = s * 10 + ch - '0';
        ch = getchar();}
    return s * w;
}
int tr[MAX];
int main()
{
    int n, k;
    deque<int>q;//雙向隊列
    cin>>n>>k;
    for(int i = 1; i <= n; i++)
    tr[i] = IntRead();
    for(int i = 1; i <= n; ++i){
        while (!q.empty() && tr[i] < tr[q.back()]) {
            q.pop_back();//去尾
        }
        q.push_back(i);//入隊
        if(i >= k){//從第k個開始，後面都得輸出
            while (!q.empty() && i - q.front() + 1 > k) {
                q.pop_front();//去頭
            }
            if(i == k) cout<<tr[q.front()];//控制空格的輸出
            else cout<<' '<<tr[q.front()];
        }
    }
    cout<<endl;
    q.clear();//清空隊列
    for(int i = 1; i <= n; i++){
        while (!q.empty() && tr[q.back()] < tr[i]) {
            q.pop_back();
        }
        q.push_back(i);
        if(i >= k){
            while (!q.empty() && i - q.front() + 1 > k) {
                q.pop_front();
            }
            if(i == k)
                cout<<tr[q.front()];
            else
                cout<<' '<<tr[q.front()];
        }
    }
    cout<<endl;
}

思路2:

手寫隊列

head代表隊列頭，tail代表隊列尾

結構體的q數組即為「雙向隊列」，其id用來記錄下標，val來記錄值

還是那四步，去尾入隊去頭取解。

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 1000000 + 5
typedef  long long ll ;
inline int IntRead(){//int的快讀
    char ch = getchar();
    int s = 0, w = 1;
    while(ch < '0' || ch > '9'){
        if(ch == '-') w = -1;
        ch = getchar();}
    while(ch >= '0' && ch <= '9'){
        s = s * 10 + ch - '0';
        ch = getchar();}
    return s * w;
}
int tr[MAX], n, k;
struct ran{
    int id, val;
}q[MAX];

void getmin(){
    int head = 1, tail = 0;//初始化
    for(int i = 1; i <= n; ++i){
        while (head <= tail && tr[i] < q[tail].val) tail--;//去尾
        q[++tail].id = i;//入隊的時候記得要記錄兩部分
        q[tail].val = tr[i];
        while (i - q[head].id + 1 > k) head++;//去頭
        if(i >= k){
            if(i == k)cout<<q[head].val;//控制空格，防止PE
            else cout<<' '<<q[head].val;
        }
    }
    cout<<endl;
}

void getmax(){
    int head = 1, tail = 0;
    for(int i = 1; i <= n; ++i){
        while (head <= tail && q[tail].val < tr[i]) tail--;
        q[++tail].id = i;
        q[tail].val = tr[i];
        while (i - q[head].id + 1 > k) head++;
        if(i >= k){
            if(i == k)cout<<q[head].val;
            else cout<<' '<<q[head].val;
        }
    }
    cout<<'\n';
}

int main()
{
    cin>>n>>k;
    for(int i = 1; i <= n; ++i) tr[i] = IntRead();
    getmin();
    getmax();
    return 0;
}

我看了一下這兩個的時間差的不多，2ms，我感覺還是dequeue好寫一些，嘎嘎，感覺寫成函數更美觀一點哎=(^.)=

Tags: 演算法