单调队列
暴力枚举(双指针) 超时
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=1e6+10;
int a[N];
vector<int> m1,m2;
int n,k;
typedef pair<int,int> PII;
PII find(int l,int r){
int minz=0x3f3f3f3f;
int maxz=-0x3f3f3f3f;
for(int i=l;i<=r;i++){
minz=min(minz,a[i]);
maxz=max(maxz,a[i]);
}
PII t={minz,maxz};
return t;
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
scanf("%d ",&a[i]);
}
int l=1;
int r=k;
while(r!=n+1){
m1.push_back(find(l,r).first);
m2.push_back(find(l,r).second);
l++;
r++;
}
for(auto& v:m1){
printf("%d ",v);
}
puts("");
for(auto& v:m2){
printf("%d ",v);
}
}
单调队列的使用(维护最小值)
维护操作可以用双端队列,单调队列维护区间的下标,每次循环的操作:
1.队尾出队:若a[i]<队尾元素m,对队尾元素依次出队,直到队列为空或a[i]大于等于队尾元素
2.队尾进队:将a[i]进队
3.队头出队:若a[i]进队后维护的区间不包含队头元素,将队头元素出队
4.若区间符合输出要求,输出队头元素
单调队列
#include<iostream>
#include<cstdio>
#include<deque>
using namespace std;
const int N=1e6+10;
deque<int> q;
int a[N];
int n,k;
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
scanf("%d ",&a[i]);
}
for(int i=1;i<=n;i++){
while(q.size()&&a[i]<a[q.back()]){ //不能写成a[i]<a[q.back()]&&q.size()
q.pop_back();
}
q.push_back(i);
if(i-k>=1&&a[q.front()]==a[i-k]){
q.pop_front();
}
if(i>=k){
printf("%d ",a[q.front()]);
}
}
puts("");
q.clear();
for(int i=1;i<=n;i++){
while(q.size()&&a[i]>a[q.back()]){ //不能写成a[i]<a[q.back()]&&q.size()
q.pop_back();
}
q.push_back(i);
if(i-k>=1&&a[q.front()]==a[i-k]){
q.pop_front();
}
if(i>=k){
printf("%d ",a[q.front()]);
}
}
}