与普通队列不同单调队列:队尾进队和出队 队头进队维护子序列的单调性特点1.队尾出队的条件:队列不是空的 且新元素更优 队中旧元素队尾出队2.每个元素必然从队尾进队一次3.队头出队的条件:队头元素滑出了窗口注意:队列中存储的是下标 方便判断队头出队单调队列的性质队列中的元素其对应在原来的列表中的顺序必须是单调递增的。队列中元素的大小必须是单调递*(增/减/甚至是自定义也可以)在每次加入或者删除元素时都保持序列里的元素有序即队首元素始终是最小值或者最大值在维护最小值的时候 :被删掉的大数再也不会回来只要新数比队尾更小、更晚过期队尾的大数就永远失去了成为窗口最小值的资格直接被淘汰 在维护最大值的时候 同样如此例题P1886代码// 滑动窗口单调队列#includebits/stdc.h #define endl \n #define ll long long #define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); const int N1000010; ll a[N],q[N],ma[N],mi[N]; using namespace std; int main() { IOS ll n,k; cinnk; for(ll i1;in;i) { cina[i]; } //维护窗口最小值 ll h1,t0; //清空队列 for(ll i1;in;i) { while(hta[q[t]]a[i]) { t--; //队尾出队队列不空且新元素更优 } q[t]i; //队尾入队存储下标 方便判断队尾出队 if(q[h]i-k1) h; if(ik) couta[q[h]] ; } coutendl; //维护窗口最大值 h1; t0; for(ll i1;in;i) { while(hta[q[t]]a[i]) { t--; } q[t]i; if(q[h]i-k1) h; if(ik) couta[q[h]]endl; } }
与普通队列不同单调队列:队尾进队和出队 队头进队维护子序列的单调性特点1.队尾出队的条件:队列不是空的 且新元素更优 队中旧元素队尾出队2.每个元素必然从队尾进队一次3.队头出队的条件:队头元素滑出了窗口注意:队列中存储的是下标 方便判断队头出队单调队列的性质队列中的元素其对应在原来的列表中的顺序必须是单调递增的。队列中元素的大小必须是单调递*(增/减/甚至是自定义也可以)在每次加入或者删除元素时都保持序列里的元素有序即队首元素始终是最小值或者最大值在维护最小值的时候 :被删掉的大数再也不会回来只要新数比队尾更小、更晚过期队尾的大数就永远失去了成为窗口最小值的资格直接被淘汰 在维护最大值的时候 同样如此例题P1886代码// 滑动窗口单调队列#includebits/stdc.h #define endl \n #define ll long long #define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); const int N1000010; ll a[N],q[N],ma[N],mi[N]; using namespace std; int main() { IOS ll n,k; cinnk; for(ll i1;in;i) { cina[i]; } //维护窗口最小值 ll h1,t0; //清空队列 for(ll i1;in;i) { while(hta[q[t]]a[i]) { t--; //队尾出队队列不空且新元素更优 } q[t]i; //队尾入队存储下标 方便判断队尾出队 if(q[h]i-k1) h; if(ik) couta[q[h]] ; } coutendl; //维护窗口最大值 h1; t0; for(ll i1;in;i) { while(hta[q[t]]a[i]) { t--; } q[t]i; if(q[h]i-k1) h; if(ik) couta[q[h]]endl; } }
