单调队列

Bertha 。 2022-05-18 10:42 252阅读 0赞

### 定义 ###

单调队列就是具有单调性质的队列，即单调递减或单调递增的队列。

### 用途 ###

在长度为n的数组中，从1到n-m+1分别为起点的连续的m个区间长度中求出最大值或最小值

### 处理过程 ###

**进队操作：**将进队的元素为e，从队尾往前扫描，直到找到一个不大于e的元素d，将e放在d之后，舍弃e之后的所有元素；如果没有找到这样一个d，则将e放在队头(此时队列里只有这一个元素)。（这是维护单调递增性，如果要维护单调递减性，就找大于e的元素d，将e放在d之后，舍弃e之后的所有元素）

**出队操作：**取队首元素出队

### 基本思想 ###

维护队首元素作为答案，去掉多余的元素（维护单调性）。

### 时间复杂度 ###

每个元素最多进队一次，出队一次，摊排分析下来仍然是 O(1)，总复杂度为复杂度O(n)。

### 例题 ###

[http://poj.org/problem?id=2823][http_poj.org_problem_id_2823]（单调队列模板）

题意：输入n和m，n代表数组的长度，m代表连续区间的长度，找出每个连续m个区间长度中的最大值和最小值。接下来输入n个数。

思路：这个问题相当于一个数据流（数列a）在不断地到来，而数据是不断过期的，相当于我们只能保存有限的数据（sliding window中的数据，此题中就是窗口的宽度w），对于到来的查询（此题中查询是每时刻都有的），我们要返回当前滑动窗口中的最大值\\最小值。注意，元素是不断过期的。

解决这个问题可以使用一种叫做单调队列的数据结构，它维护这样一种队列：

a)从队头到队尾，元素在我们所关注的指标下是递减的（严格递减，而不是非递增），比如查询如果每次问的是窗口内的最小值，那么队列中元素从左至右就应该递增，如果每次问的是窗口内的最大值，则应该递减，依此类推。这是为了保证每次查询只需要取队头元素。

b)从队头到队尾，元素对应的时刻（此题中是该元素在数列a中的下标）是递增的，但不要求连续，这是为了保证最左面的元素总是最先过期，且每当有新元素来临的时候一定是插入队尾。

满足以上两点的队列就是单调队列，首先，只有第一个元素的序列一定是单调队列。

那么怎么维护这个单调队列呢？无非是处理插入和查询两个操作。

对于插入，由于性质b，因此来的新元素插入到队列的最后就能维持b)继续成立。但是为了维护a)的成立，即元素在我们关注的指标下递减，从队尾插入新元素的时候可能要删除队尾的一些元素，具体说来就是，找到第一个大于（在所关注指标下）新元素的元素，删除其后所有元素，并将新元素插于其后。**因为所有被删除的元素都比新元素要小，而且比新元素要旧，因此在以后的任何查询中都不可能成为答案，所以可以放心删除。**

对于查询，由于性质b，因此所有该时刻过期的元素一定都集中在队头，因此利用查询的时机删除队头所有过期的元素，在不含过期元素后，队头得元素就是查询的答案（性质a），将其返回即可。

代码：

#include <iostream>
    #include<cstdio>
    using namespace std;
    const int Max = 1000004;
    int n,m,a[Max],v[Max],mn[Max],mx[Max],head,tail;//v代表队列，存放的是数组a的下标
    void getmin()
    {
        head = 1;tail = 0;//代表队列的头和尾
        for(int i = 1; i < m; i++)//先把队列中初始的值确定
        {
            while(head <= tail && a[v[tail]] >= a[i]) tail--;
            v[++tail] = i;
        }
        for(int i = m; i <= n; i++)
        {
            while(head <= tail && a[v[tail]] >= a[i]) tail--;//如果要插入的数比队尾的数还要大的话，就说明对答案没有影响，就可以删除此元素
            v[++tail] = i;
            while(v[head] < i-m+1) head++;
            //mn[i-m+1] = a[v[head]];
            printf("%d ",a[v[head]]);//输出队首元素，即最小值
        }
        cout << endl;
    }
    void getmax()//同理可得
    {
        head = 1;tail = 0;
        for(int i = 1; i < m; i++)
        {
            while(head <= tail && a[v[tail]] <= a[i]) tail--;
            v[++tail] = i;
        }
        for(int i = m; i <= n; i++)
        {
            while(head <= tail && a[v[tail]] <= a[i]) tail--;
            v[++tail] = i;
            while(v[head] < i-m+1) head++;
            //mx[i-m+1] = a[v[head]];
            printf("%d ",a[v[head]]);
        }
        cout << endl;
    }
    int main()
    {
        cin >> n >> m;
        for(int i = 1; i <= n; i++)
            cin >> a[i];
        getmin();
        getmax();
    }

[http_poj.org_problem_id_2823]: http://poj.org/problem?id=2823