洛谷 P1886 滑动窗口 题解

每日一题 day26 打卡

Analysis

单调队列模板

对于每一个区间，有以下操作：

1、维护队首（就是如果你已经是当前的m个之前那你就可以被删了,head++）

2、在队尾插入（每插入一个就要从队尾开始往前去除冗杂状态）

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define int long long

 #define maxn 1000000+10

 using namespace std;

 inline int read()

 {

     int x=;

     bool f=;

     char c=getchar();

     for(; !isdigit(c); c=getchar()) if(c=='-') f=;

     for(; isdigit(c); c=getchar()) x=(x<<)+(x<<)+c-'';

     if(f) return x;

     return -x;

 }

 inline void write(int x)

 {

     if(x<){putchar('-');x=-x;}

     if(x>)write(x/);

     putchar(x%+'');

 }

 int n,k;

 int a[maxn];

 int deque[maxn],deque_num[maxn];

 inline void solve_min()

 {

     int head=,tail=;

     for(int i=;i<=n;i++)

     {

         while(head<=tail&&deque[tail]>=a[i]) tail--;

         deque[++tail]=a[i];

         deque_num[tail]=i;

         while(head<=tail&&deque_num[head]<=i-k) head++;

         if(i>=k)

         {

             write(deque[head]);

             printf(" ");

         }

     }

     printf("\n");

 }

 inline void solve_max()

 {

     int head=,tail=;

     for(int i=;i<=n;i++)

     {

         while(head<=tail&&deque[tail]<=a[i]) tail--;

         deque[++tail]=a[i];

         deque_num[tail]=i;

         while(head<=tail&&deque_num[head]<=i-k) head++;

         if(i>=k)

         {

             write(deque[head]);

             printf(" ");

         }

     }

 }

 signed main()

 {

     n=read();k=read();

     for(int i=;i<=n;i++) a[i]=read();

     solve_min();

     memset(deque,,sizeof(deque));

     memset(deque_num,,sizeof(deque_num));

     solve_max();

     return ;

 }

 /*

 10 3

 -94 21 24 73 38 77 11 73 9 -88

 -94 21 24 38 11 11 9 -88

 24 73 73 77 77 77 73 73

 */

请各位大佬斧正