初识单调队列(滑动窗口最小值)

性质

单调队列,顾名思义,是一个“单调”的队列。
如何便是单调?单调递增/递减。假设 下面说的都是单调递减队列。

插入元素时,如何维护单调队列的单调性? 这是单调队列中最基础的问题。
解决方法往往很粗暴:先把队尾所有小于插入元素的都删除,然后插入元素。 这样就有序了。但是有个问题,为什么可以直接删除那些元素?

与要维护的东西的性质有关。

显然,我是懒得手打循环队列的。上STL大法——双端队列。

#include <deque>
using namespace std;

int main()
{
    deque <int> q;
    q.push_front(1);             //队首插入1
    printf("%d\n",q[0]);         //滋磁随机访问!
    q.push_back(2);              //队尾插入2
    q.push_back(3);              //队尾插入3
    q.pop_back();                //弹出队尾元素
}

例题:滑动窗口

一个长度为n的序列,有一个长度为k窗口在其中滑动。 求出:每一个位置,窗口中元素的最大值、最小值。

Example:

窗口位置……………….最小值….最大值
[ 1 3 -1 ] -3 5 3 6 7…..-1……..3
1 [ 3 -1 -3 ] 5 3 6 7…..-3……..3
1 3 [ -1 -3 5 ] 3 6 7…..-3……..5
1 3 -1 [ -3 5 3 ] 6 7…..-3……..5
1 3 -1 -3 [ 5 3 6 ] 7……3……..6
1 3 -1 -3 5 [ 3 6 7 ]……3……..7

暴力

想题先想暴力?

对于每个窗口位置,暴力求最大最小值。 复杂度O(n∗k)。

平衡树

考虑优化上面的暴力。 根据滑动窗口的性质,每次移动只有一个元素进入、一个元素弹出。

由此,维护一个平衡树,储存元素的出现次数。取最大/最小值输出,窗口移动时删除左边元素、加入右边元素。

可以用STL的multiset(可重复集合)来处理。 复杂度O(nlogn)

单调队列

首先,我们只考虑最大值。最小值是类似的。窗口在移动,我们需要维护窗口中的最大值。

考虑下面的事实:如果有l代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+6;
int a[maxn];
deque<int>q;
int main()
{
    int n,k,i;
    cin>>n>>k;//数组总长度和窗口大小 
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    for(int i=0;i<n;i++)
    {
        while(!q.empty()&&a[i]<a[q.back()])
            q.pop_back();
        q.push_back(i);
        while(q.back()-q.front()+1>k)//判断是否超过窗口大小
            q.pop_front();
        if(i>=k-1)
            cout<<a[q.front()]<<" ";
    }
    cout<<endl;
    return 0;
}

参考博客:https://ruanx.pw/post/%E5%8D%95%E8%B0%83%E9%98%9F%E5%88%97.html

发表评论

电子邮件地址不会被公开。 必填项已用*标注