算法
单调队列
题目描述
给出一个数组，有固定大小窗口在数组上从左到右滑动，现要求求出每个窗口中最大值与最小值。
解题思路
以求窗口中最小值为例，因为滑动时去除窗口中较大且靠左的数字对于窗口的最小值没有任何影响，所以我们使用单调上升队列（双向队列）保存窗口中可能成为最小值的元素，移动窗口时维护此单调上升队列即可；
同理，最大值使用单调下降队列即可。
代码
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstdio>
using namespace std;
const int Maxn=1000010;
int a[Maxn];
int main() {
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
deque<int> qd,qc;
for(int i=1;i<k;i++){
while(!qd.empty()){
if(a[qd.front()]>a[i])
qd.pop_front();
else
break;
}
qd.push_front(i);
while(!qc.empty()){
if(a[qc.front()]<a[i])
qc.pop_front();
else
break;
}
qc.push_front(i);
}
for(int i=k;i<=n;i++){
while(!qd.empty()){
if(a[qd.front()]>a[i])
qd.pop_front();
else
break;
}
qd.push_front(i);
if(i-k==qd.back())
qd.pop_back();
printf("%d ",a[qd.back()]);
}
cout<<endl;
for(int i=k;i<=n;i++){
while(!qc.empty()){
if(a[qc.front()]<a[i])
qc.pop_front();
else
break;
}
qc.push_front(i);
if(i-k==qc.back())
qc.pop_back();
printf("%d ",a[qc.back()]);
}
cout<<endl;
return 0;
}
题目总结
使用单调队列的性质；注意题目中的细节处理，如单调上升队列应为单调非下降队列，即保存相等的值。
