Time Limit: 12000MS | Memory Limit: 65536K | |
Total Submissions: 41844 | Accepted: 12384 | |
Case Time Limit: 5000MS |
Description
The array is [1 3 -1 -3 5 3 6 7], and k is 3.
Window position | Minimum value | Maximum value |
---|---|---|
[1 3 -1] -3 5 3 6 7 | -1 | 3 |
1 [3 -1 -3] 5 3 6 7 | -3 | 3 |
1 3 [-1 -3 5] 3 6 7 | -3 | 5 |
1 3 -1 [-3 5 3] 6 7 | -3 | 5 |
1 3 -1 -3 [5 3 6] 7 | 3 | 6 |
1 3 -1 -3 5 [3 6 7] | 3 | 7 |
Your task is to determine the maximum and minimum values in the sliding window at each position.
Input
Output
Sample Input
8 3
1 3 -1 -3 5 3 6 7
Sample Output
-1 -3 -3 -3 3 3
3 3 5 5 6 7
双端队列介绍:
deque和vector一样都是标准模板库中的内容,deque是双端队列,在接口上和vector非常相似,在许多操作的地方可以直接替换。假如读者已经能够有效地使用vector容器,下面提供deque的成员函数和操作,进行对比参考。
deque<type>q;
q.empty():判断队列是否为空
q.front() ,q.back() 队列的首元素和尾元素
q.begin() ,q.end() 返回队列首元素和结尾地址
q.push_front() ,q.push_back() 分别在队首和队尾插入元素
q.pop_front() ,q.pop_back() 删除首元素和尾元素
q.size() 返回容器中元素的个数
q.clear() 清空所有元素
本题最好采用模拟队列,缩短时限,分析怎样维护递增单调队列,开一个结构体要有id序号,和v值两个内容,首先当队列为空的时候,加入第一个元素;对于下一个将要加入的元素,把该元素a的大小和队尾的元素大小tail进行比较,如果a>tail,则移除尾元素,继续比较,直到a<=tail时把a加入到队列的尾部,当k个连续的数列向后移动时,队列中的前面的元素可能已经不再此范围内了,所以还要判断首元素的序号是不是在此时的范围内,如果不在,这删除首元素(即head++)直到满足条件为止,这样便可以维护一个单调递增队列
当维护单调递减序列的道理同上
程序:
#include"cstdio"
#include"cstring"
#include"cstdlib"
#include"cmath"
#include"string"
#include"map"
#include"cstring"
#include"algorithm"
#include"iostream"
#include"set"
#include"queue"
#include"stack"
#define inf 1000000000000
#define M 1000009
#define LL long long
#define eps 1e-12
#define mod 1000000007
#define PI acos(-1.0)
using namespace std;
int a[M],maxi[M],mini[M];
struct node
{
int v,id;
node(){}
node(int id,int v)
{
this->v=v;
this->id=id;
}
}qmin[M*2],qmax[M*2];
int main()
{
int n,k;
while(scanf("%d%d",&n,&k)!=-1)
{
int minhead=0,mintail=0;
int maxhead=0,maxtail=0;
int cnt=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(i<=k)
{
while(mintail>minhead&&a[i]<qmin[mintail-1].v)
{
mintail--;
}
qmin[mintail++]=node(i,a[i]);//把前k个元素入队 while(maxtail>maxhead&&a[i]>qmax[maxtail-1].v)
{
maxtail--;
}
qmax[maxtail++]=node(i,a[i]);
}
}
mini[cnt]=qmin[minhead].v;
maxi[cnt++]=qmax[maxhead].v;
for(int i=k+1;i<=n;i++)
{
while(mintail>minhead&&a[i]<qmin[mintail-1].v)//删除比a[i]小的尾元素
{
mintail--;
}
qmin[mintail++]=node(i,a[i]);
while(mintail>minhead&&i-k>=qmin[minhead].id)//删除不再范围内的首元素
{
minhead++;
} while(maxtail>maxhead&&a[i]>qmax[maxtail-1].v)
{
maxtail--;
}
qmax[maxtail++]=node(i,a[i]);
while(maxtail>maxhead&&i-k>=qmax[maxhead].id)
{
maxhead++;
}
mini[cnt]=qmin[minhead].v;
maxi[cnt++]=qmax[maxhead].v;
}
printf("%d",mini[0]);
for(int i=1;i<cnt;i++)
printf(" %d",mini[i]);
printf("\n%d",maxi[0]);
for(int i=1;i<cnt;i++)
printf(" %d",maxi[i]);
printf("\n");
}
return 0;
}