Void-7's

洛谷P1886 滑动窗口 /【模板】单调队列

luogu.png

国庆借机会间歇性做了点洛谷的算法题,主要目的还是为了重新学习算法和数据结构吧。学习+做题的反馈过程还是很有效的,前两年错过了太多机会。希望这次算法能够好好学一下。博客一直也没更新,虽然没人看,但也得给自己学习做点记录吧,抱着这样的想法从P1886开个头吧。

虽然对算法一无所知,但是查了下资料发现这题貌似还挺经典的。单调队列,边学边做。

原来是看pilipili某Up讲的方法来抄的写的,数组实现。事实证明这种做法确实在时间和空间复杂度上都比STL用deque来实现表现得更好(758ms vs 1.17s)。不过STL毕竟更直观易懂,适合我这样的算法菜鸡。下面分别附上两种方法:

利用数组实现:

#include<cstdio>
int n,k,s[1000001],que[1000001],st,ed;

//求最小值:维护一个递增的单调队列
void push_min(int p){
    while(st<=ed && s[que[ed]]>=s[p]){
        ed--;
    }
    ed++;
    que[ed]=p;
}

//队首pop窗口外的元素
void pop(int p){
    while(st<=ed && que[st]<=p) st++;
}

//求最大值:维护一个递减的单调队列
void push_max(int p){
    while(st<=ed && s[que[ed]]<=s[p]){
        ed--;
    }
    ed++;
    que[ed]=p;
}

int main(){
    scanf("%d%d",&n,&k);
    //先将原始序列存到数组中
    for(int i=1;i<=n;i++){
        scanf("%d",s+i);
    }
    /*求当前窗口的最小值*/
    st=1;ed=0;
    for(int i=1;i<k;i++){
        push_min(i);
    }
    for(int i=k;i<=n;i++){
        pop(i-k);
        push_min(i);
        printf("%d ",s[que[st]]);
    }
    putchar('\n');
    /*求当前窗口的最大值*/
    st=1;ed=0;//记得重置队列,数组只需要重置st/ed
    for(int i=1;i<k;i++){
        push_max(i);
    }
    for(int i=k;i<=n;i++){
        pop(i-k);
        push_max(i);
        printf("%d ",s[que[st]]);
    }
    return 0;
}

C++

利用STL< deque >双端队列实现:

#include <cstdio>
#include <deque>
#include <ctype.h>
using namespace std;
int a[1000010];
typedef pair<int, int> par;
//利用pair来存储序列元素的索引,方便后面pop窗口外元素
deque<par> que1,que2;
int n, k;
//快读
inline int read()
{
    register int x = 0, y = 0;
    register char ch = getchar();
    for (; !isdigit(ch); ch = getchar())
        if (ch == '-')
            y = 1;
    for (; isdigit(ch); ch = getchar())
        x = (x << 3) + (x << 1) + (ch ^ 48);
    return y ? -x : x;
}

void push_min(deque<par> &que,par &x)
{
    while (!que.empty() && que.back().first >= x.first)
        que.pop_back();
    que.push_back(x);
}

void push_max(deque<par> &que,par &x)
{
    while (!que.empty() && que.back().first <= x.first)
        que.pop_back();
    que.push_back(x);
}

int main()
{
    n = read();
    k = read();
    int min;
    int tmp;
    for (int i = 1; i <= n; i++)
        a[i] = read();
    for (int i = 1; i < k; i++){
        tmp = a[i];
        par item(tmp, i);
        push_min(que1,item);
    }
    for (int i = k; i <= n; i++){
        tmp = a[i];
        par item(tmp, i);
        //记得判空呀,没判空第三个点RE,因为第三个点是k=1
        while (!que1.empty()&&i - que1.front().second >= k)
            que1.pop_front();
        push_min(que1,item);
        printf("%d ", que1.front());
    }
    putchar('\n');
    
    for (int i = 1; i < k; i++){
        tmp = a[i];
        par item(tmp, i);
        push_max(que2,item);
    }
    for (int i = k; i <= n; i++){
        tmp = a[i];
        par item(tmp, i);
        while (!que2.empty()&&i - que2.front().second >= k)
            que2.pop_front();
        push_max(que2,item);
        printf("%d ", que2.front());
    }
    return 0;
}