首页 > 代码库 > 滑动窗口

滑动窗口

单调队列

 

洛谷 P1886 滑动窗口

 

by  GeneralLiu

 

给出有n个数的序列

求所有的连续k个数

的最大值 以及 最小值

 

 

思路(就只写 MAX 了 , MIN 一个道理,懒得写了)

 

 

目标是  长度为k的窗口中的MAX 且窗口从左向右滑动

 

在滑动过程中  

   有时会进来一个很大的数 比 前面所有都大

     假设 在这个数 出去之前 不会进来比它大的数

     那么在它出去之前 他会一直代表 着窗口的 MAX

     那把窗口分成两部分 (不考虑 MAX 本身单独一部分)

    1 MAX 左边的所有数

    2 MAX 右边的所有数

   因为 “在它出去之前 他会一直代表 着窗口的 MAX”

   所以 第一部分是 没有价值的 

   

          而 第二部分 肯定 会比 MAX 晚出去 

    在 MAX 出去后 再 体现价值

 

所以说 一直去掉 “第一部分” 即 没有价值 的部分

  便维护了一个单调递减的 “队列”

  这个“队列”不是严格按照 FIFO first-in-first-out

  你想想 排队买饭时发现 排错队列了

  你难道要 排到你(你到了队头)时 再出去吗?

  所以 这个“队列”的队尾也是可以出队的

 

每次 输出 队头元素 (单调减,队头最大)

  等到“该出队”时(代码 34 行)再出队 即可

 

 

代码

 

 1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 1000006 4 int n,k,que1[N],ans1[N],ans2[N],h1=1,h2=1,t1,t2,que2[N],pos1[N],pos2[N]; 5 int read(){  //  读入优化  6     int ans=0,f=1; 7     char ch=getchar(); 8     for(;!isdigit(ch);ch=getchar()) 9         if(ch==-)10             f=-1;11     for(;isdigit(ch);ch=getchar())12         ans=ans*10+ch-0;13     return ans*f;14 }15 int main(){16     n=read(),k=read();17     for(int a,i=1;i<=n;i++){18           a=read();19           20           // 维护 单调减  21           for(;t1>=h1&&a>=que1[t1];t1--);22           que1[++t1]=a;23           pos1[t1]=i;24           25           // 维护 单调增 26           for(;t2>=h2&&a<=que2[t2];t2--);27           que2[++t2]=a;28           pos2[t2]=i;29           30           if(i>=k){31               ans1[i]=que1[h1]; //储存答案 32               ans2[i]=que2[h2];33               34               //该出队了 35               if(pos1[h1]==i-k+1)h1++;  36               if(pos2[h2]==i-k+1)h2++;37           }38     }39     for(int i=k;i<=n;i++) // 最小的 40         cout<<ans2[i]<<" ";41     cout<<endl;42     for(int i=k;i<=n;i++) // 最大的 43         cout<<ans1[i]<<" ";44 }

 

滑动窗口