Description
An array of size n ≤ 106 is given to you. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example:Your task is to determine the maximum and minimum values in the sliding window at each position.
Input
The input consists of two lines. The first line contains two integers n and k which are the lengths of the array and the sliding window. There are n integers in the second line.Output
There are two lines in the output. The first line gives the minimum values in the window at each position, from left to right, respectively. The second line gives the maximum values.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;
}
