poj-2823 Sliding Window

poj-2823 Sliding Window

基礎的單調隊列，維護一個單調遞增和一個單調遞減隊列即可。

#include
#define M 2000005
int a[M],Q[M],I[M];
int i,n,k;
void getMax() //求每個區間的最大值 維護一個單調遞減的隊列，則隊首元素就是這個區間的最大值，如果不在范圍內就隊首元素加1
{
    int head=1,tail=0; //隊首指針   隊尾指針
    for(i=1;i=a[i])tail--;
        tail++;
        Q[tail]=a[i];I[tail]=i;
    }
    for(i=k;i<=n;i++)
	{
        while(head<=tail&&Q[tail]>=a[i])tail--;
        tail++;
        Q[tail]=a[i];I[tail]=i;
        while(I[head]<=i-k) head++;
        printf("%d ",Q[head]);
    }
}
int main()
{
    while(scanf("%d %d",&n,&k)!=EOF)
    {
    for(i=1;i<=n;i++) scanf("%d",&a[i]);
    getMin();
    printf("\n");
    getMax();
    }
    return 0;
}