一道题A两遍，舒适。

题目描述

现在有一堆数字共N个数字（N<=10^6），以及一个大小为k的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

例如：

The array is [1 3 -1 -3 5 3 6 7], and k = 3.

输入输出格式

输入格式

输入一共有两行，第一行为n,k。

第二行为n个数(<INT_MAX).

输出格式

输出共两行，第一行为每次窗口滑动的最小值

第二行为每次窗口滑动的最大值

INPUT & OUTPUT’s examples

Input’s eg #1

1 2	8 3 1 3 -1 -3 5 3 6 7

Output’s eg #1

1 2	-1 -3 -3 -3 3 3 3 3 5 5 6 7

数据说明

50%的数据，$n \leq 10^5$

100%的数据，$n \leq 10^6$

分析

又是RMQ问题，不过指定区间不是输入数据，而是滑动的指定长度的一段范围。

~~所以线段树大法好啊！~~

$n \leq 10^6$你写个锤子线段树！

那么，我们就可以考虑单调队列了。

维护两个单调队列，一个递增，一个递减，维护最值查询。

然后开两个线性表Max[]和Min[]记录指定长度内单调队列中的最值（队头）

代码

 /* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
using namespace std;
namespace FastIO{
    const int BUFSIZE=1<<20;
    char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
    char obuf[BUFSIZE],*os=obuf,*ot=obuf+BUFSIZE;
    inline char getch(){
        if(is==it)
            it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is==it)?EOF:*is++;
    }
    inline int getint(){
        int res=0,neg=0,ch=getch();
        while(!(isdigit(ch)||ch=='-')&&ch!=EOF)
            ch=getch();
        if(ch=='-'){
            neg=1;ch=getch();
        }
        while(isdigit(ch)){
            res=(res<<3)+(res<<1)+(ch-'0');
            ch=getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os=obuf;
    }
    inline void putch(char ch){
        *os++=ch;
        if(os==ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res<0){
            putch('-');
            res=-res;
        } 
        int top=0;
        while(res){
            q[top++]=res%10+'0';
            res/=10;
        }
        while(top--)	putch(q[top]);
    }
} 
using namespace FastIO;
/* definitions */
const int MAXN = 1e6+7;
int win[MAXN],Max[MAXN],Min[MAXN];
int n,m;
struct Node{
	int val;
	int index;
}; 
Node Q[MAXN];
/* functions */
inline void MinVal(){
	int i,head=0,tail=1;
	for(i=1;i<=m-1;i++){
		while(head<=tail && Q[tail].val>=win[i])tail--;
		Q[++tail].val=win[i];
		Q[tail].index=i;
	}
	for(;i<=n;i++){
		while(head<=tail&&Q[tail].val>=win[i])tail--;
		Q[++tail].val=win[i]; 
		Q[tail].index=i;
		while(Q[head].index<i-m+1)head++;
		Min[i-m+1]=Q[head].val;
	} 
}
inline void MaxVal(){
	int i,head=0,tail=1;
	for(i=1;i<=m-1;i++){
		while(head<=tail&&Q[tail].val<=win[i])tail--;
		Q[++tail].val=win[i];
		Q[tail].index=i;
	}
	for(;i<=n;i++){
		while(head<=tail&&Q[tail].val<=win[i])tail--;
		Q[++tail].val=win[i];
		Q[tail].index=i;
		while(Q[head].index<i-m+1)head++;
		Max[i-m+1]=Q[head].val;
	}
}
inline void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&win[i]);
	MinVal();
	MaxVal();
}
int main(int argc,char *argv[]){
	init();
	for(int i=1;i<=n-m+1;i++){
		if(i==1)printf("%d",Min[i]);
		else printf(" %d",Min[i]);
	} 
	printf("\n");
	for(int i=1;i<=n-m+1;i++){
		if(i==1)printf("%d",Max[i]);
		else printf(" %d",Max[i]);
	}
	printf("\n");
	return 0;
}

POJ2823&洛谷P1886题解