数据结构 | 单调队列

作者: 0与1的邂逅 | 来源:发表于2019-10-10 00:07 被阅读0次

写在前面：

最近接触到一种挺有意思的数据结构——单调队列，可以用来维护（给定大小的）区间的最值，其时间复杂度为 $O(n)$ ，其中n为序列的元素个数。

1. 单调队列：

单调队列，顾名思义，是一种具有单调性的队列。众所周知，单调性有单调递增和单调递减两种，相应的单调队列也分为单调递增队列和单调递减队列两种。

单调递增队列：保证队列头元素一定是当前队列的最小值，用于维护区间的最小值。
单调递减队列：保证队列头元素一定是当前队列的最大值，用于维护区间的最大值。

2. 一个简单例子：

在说具体怎么实现一个单调队列之前，先来一个简单的例子，感受一下。

给定数列： $3 ，1 ，5 ， 7 ，4 ，2 ， 1$ ，现在要维护 区间长度为 $3$ 的最大值。

操作序号	操作	队列中元素	指定区间最大值
①	$3$ 入队	$3$	区间大小不符合
②	$1$ 入队	$3,1$	区间大小不符合
③	$3,1$ 出队， $5$ 入队	$5$	区间 $[1,3]$ 的最大值为 $5$
④	$5$ 出队， $7$ 入队	$7$	区间 $[2,4]$ 的最大值为 $7$
⑤	$4$ 入队	$7,4$	区间 $[3,5]$ 的最大值为 $7$
⑥	$2$ 入队	$7,4,2$	区间 $[4,6]$ 的最大值为 $7$
⑦	$1$ 入队， $7$ 出队	$4,2,1$	区间 $[5,7]$ 的最大值为 $4$

可以发现队列中的元素都是单调递减的（不然也就不叫单调递减队列啦），同时既有入队列的操作、也有出队列的操作。

3. 实现流程：

实现单调队列，主要分为三个部分：

去尾操作 ：队尾元素出队列。当队列有新元素待入队，需要从队尾开始，删除影响队列单调性的元素，维护队列的单调性。(删除一个队尾元素后，就重新判断新的队尾元素)

去尾操作结束后，将该新元素入队列。

删头操作 ：队头元素出队列。判断队头元素是否在待求解的区间之内，如果不在，就将其删除。（这个很好理解呀，因为单调队列的队头元素就是待求解区间的极值）
取解操作 ：经过上面两个操作，取出 队列的头元素 ，就是 当前区间的极值 。

3.1 去尾操作：队尾元素出队列

假设需要维护一个 区间长度为 $L$ 的 最大值，显然，我们需要一个 单调递减队列。

现在有一个新元素 $new$ （序号为 $new\_id$ ）待放入队列，在新元素 $new$ 入队列之前，需要先执行下面的操作：

如果当前 队列为空，则 直接将 $new$ 放入队列 。否则，执行下一步。
（假设队列的尾元素为 $rear$ ）当前 队列不为空 。

如果 $rear<new$ ，则 尾元素 $rear$ 出队列，直到 当前队列为空 或者 $rear<new$ 不再满足。紧接着，元素 $new$ 入队列。
如果 $rear>=new$ ，直接将元素 $new$ 放入队列。

3.2 删头操作：队头元素出队列

将新元素 $new$ 入队列之后，我们还需要判断当前队列中 队头元素 是否在 待求解的区间范围 内。

假设队列的头元素为 $front$ （序号为 $front\_id$ ）。

如果此时当前 队列不为空 ，且 $front\_id<new\_id-L+1$ ，那么将 队列头元素 $front$ 出队列 。不断重复此过程，直至 $front\_id>=new\_id-L+1$ 。
(也就是说，将队列中序号不在 区间 $[\ new\_id-L+1,new\_id\ ]$ 的元素删除)

3.3 取解操作

经过上面的操作，此时 队列的头元素 就是 区间 $[\ new\_id-L+1,new\_id\ ]$ 的最大值。

上面说到的区间下标是从 $1$ 开始的，相应的，队列的头元素下标也要从 $1$ 开始，删掉头元素的条件为 $front\_id<new\_id-L+1$ 。

但是如果区间下标是从 $0$ 开始的，相应的，队列的头元素下标也要从 $0$ 开始，删除头元素的条件就变为 $front\_id<new\_id-L$ 。

讲完了过程，怎么能少了代码呢（手动滑稽）

// 假设有 n 个元素的序列，要求解的是长度为 k 的区间的最大值
// 队列que是STL的双向队列deque
// 队列存放的是元素在序列中的序号
deque<int>que;// 双向队列
for(int i=1;i<=n;i++)
{
    while(!que.empty() && a[que.back()]<a[i])
    {
        que.pop_back();// 去尾操作
    }
    que.push_back(i);// 新元素(的序号) 入队列
    if(i>=k)// 这个很明显
    {
        while(!que.empty() && que.front()<i-k+1)
        {
            que.pop_front();// 删头操作 
        }
        cout<<a[que.front()]<<" ";// 取解操作
    }
}

3.4 单调队列的性质：

下面以单调递减队列为例。

队列里的元素是 单调递减 的。
假如维护区间长度为 $L$ 的最大值，刚入队的元素下标为 $x$ ，则队列首元素是区间 $[x-L+1,x]$ 的最大值。
由于每个元素只会入队和出队各一次，所以复杂度为 $O(n)$ 。

4. 模板题——洛谷P1886

传送门：洛谷P1886 滑动窗口

4.1 暴力枚举

如果按照 常规方法——暴力枚举，我们在求 $a[i]$ 即 $i$ ~ $i+k-1$ 区间内的最值时，要把 区间内的所有数 都 访问一遍。

对于有 $n$ 个元素的序列来说，需要比较 $n-k+1$ 次（也就是说一个长度为 $n$ 的序列，可以分成 $n-k+1$ 个长度为 $k$ 的区间）。因此，需要比较的总次数为 $(n-k+1)*k$ ，约为 $n*k$ 。故时间复杂度约为 $O(n*k)$ 。

// 暴力 O(nk) 
#include<iostream>
#include<cstdio>
using namespace std;

int n,k;
int a[1000010];
int f[1000010];// 保存每个 max，方便第二行输出 

int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    int index=0;
    for(int i=k;i<=n;i++)
    {
        int Max=-0xfffff,Min=0xfffff;
        for(int j=i-k+1;j<=i;j++)
        {
            if(a[j]>Max)Max=a[j];
            if(a[j]<Min)Min=a[j];
        }
        if(i!=n)cout<<Min<<" ";
        else cout<<Min<<endl;
        f[++index]=Max; 
    }
    cout<<endl;
    for(int i=1;i<=index;i++)
    {
        if(i!=index)cout<<f[i]<<" ";
        else cout<<f[i]<<endl;
    }
    return 0;
}

暴力枚举

我的天，暴力枚举有两个用例WA掉了，还有一个TLE（哭辽~）

4.2 单调队列：

单调队列有两种写法，一种是直接使用C++ STL 中双向队列deque，另一种是自己手写队列。

结果显示手写队列比STL的deque花费的时间要少，看来有时候手写还是挺有用的。

// 单调队列 STL deque
// O(n) 
#include<bits/stdc++.h>
using namespace std;

int n,k;
int a[1000010];
deque<int>que;

int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    // min 
    // 这里队列保存的是元素的index 
    for(int i=1;i<=n;i++)
    {
        while(!que.empty() && a[que.back()]>a[i])
        {
            que.pop_back();// 去尾 
        }
        que.push_back(i);// 入队
        if(i>=k)
        {
            while(!que.empty() && que.front()<i-k+1)
            {
                que.pop_front();// 删头 
            }
            cout<<a[que.front()]<<" ";
        } 
    }
    cout<<endl;
    while(!que.empty())que.pop_front();// 清空队列 
    // max
    for(int i=1;i<=n;i++)
    {
        while(!que.empty() && a[que.back()]<a[i])
        {
            que.pop_back();// 去尾 
        }
        que.push_back(i);
        if(i>=k)
        {
            while(!que.empty() && que.front()<i-k+1)
            {
                que.pop_front();// 去头 
            }
            cout<<a[que.front()]<<" ";
        }
    }
    cout<<endl;
    return 0;
}

STL deque

// 手写单调队列 
#include<cstdio>
#include<iostream>
using namespace std;

const int maxn=1e6+5;
int n,k,head,tail,a[maxn];

struct node
{
    // id:index val:value 
    int id,val;
}
q[maxn];// 手写队列 

inline void work_min()
{
    head=1,tail=0;
    for(int i=1;i<=n;i++)
    {
        while(head<=tail && a[i]<=q[tail].val)tail--;
        q[++tail].id=i;
        q[tail].val=a[i];
        
        while(q[head].id<=i-k)head++;
        if(i>=k)printf("%d ",q[head].val);
    }
    printf("\n");
}

inline void work_max()
{
    head=1,tail=0;//初始化 
    for(int i=1;i<=n;i++)
    {
        // 队列非空 且 待入队元素大于队列尾元素
        // 队尾元素出队 
        while(head<=tail && a[i]>=q[tail].val)tail--;// 去尾操作 
        // 新元素入队
        q[++tail].id=i; 
        q[tail].val=a[i];
        
        // 队列非空 且  index小于 i-k+1(或者说 index小于等于 i-k) 
        // 队头元素出队 
        while(q[head].id<=i-k)head++;// 删头操作 
        if(i >= k)printf("%d ", q[head].val);// 取解 
    }
    printf("\n");
}

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    work_min();
    work_max();
    return 0;
}

手写队列

手写队列 的时候，需要明确尾指针指向的是 尾元素 还是指向 尾元素的下一个 ，不同的指向对应的代码会有些许不同。（上面的代码是 指向尾元素 ）

这道题目还有其他的不错的做法，例如ST表，线段树。因为不是重点，就不列出来啦~~（主要是自己也不太会）~~

写在最后：

参考资料：

单调队列，一种挺神奇的队列，算法的思路也挺新奇的，在后面将会用到。

国庆结束啦，下一个节假日就是元旦了吧。

数据结构 | 单调队列

写在前面：

1. 单调队列：

2. 一个简单例子：

3. 实现流程：

3.1 去尾操作：队尾元素出队列

3.2 删头操作：队头元素出队列

3.3 取解操作

3.4 单调队列的性质：

4. 模板题——洛谷P1886

4.1 暴力枚举

4.2 单调队列：

写在最后：

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

算法