程式碼備份區

題意：

給n數字，以及長度k的框框，問說框框從最左邊移動到最右邊時，中間框住的數字中最大與最小的是誰

解法：

可以利用單調性，把框框內的東西由大到小排列，之後每次要加入時，就從後面往前看，若目前看到的人比較小就丟掉，直到看到比他大的人為止，並且塞在他後面

要丟掉時，就從前面往後看，把比目前要丟掉的人的ID還要小的都丟掉，直到第一個ID比要丟掉的還大為止

這樣就2對每個人都只會做到進來與出去兩次，所以是O(n)

不過POJ這題他測資卡很緊(應該是想擋O(nlogn)的解法)，所以要做IO優化

程式碼：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int num[1000100];
int q  [1000100];
int th [1000100];
int n,k;
int h,t;
char out[123];
int oNum;
int i,j;
unsigned int tmp;
int flag;
void max(){

    h = 1;
    t = 0;
    for(i=1;i<k;++i){
        while(h <=t && q[t]<num[i])--t;
        q[++t]=num[i];
        th[t]=i;
    }
    for(i=k,j=0;i<=n;++i,++j){
        while(h <=t && q[t]<num[i])--t;
        q[++t]=num[i];
        th[t]=i;
        while(th[h]<=j) ++h;

        if(q[h]==0){
            putchar('0');
        }else {
            if(q[h]>0){
                flag = 0;
                tmp = q[h];
            }else {
                flag = 1;
                tmp = -q[h];
            }
            for(oNum=0;tmp>0;tmp/=10,++oNum)out[oNum]=tmp%10+'0';
            if(flag)putchar('-');
            for(--oNum;oNum>=0;--oNum)putchar(out[oNum]);
        }
        putchar((i==n)?'\n':' ');
    }
}
void min(){
    h = 1;
    t = 0;
    for(i=1;i<k;++i){
        while(h <=t && q[t]>num[i])--t;
        q[++t]=num[i];
        th[t]=i;
    }
    for(i=k,j=0;i<=n;++i,++j){
        while(h <=t && q[t]>num[i])--t;
        q[++t]=num[i];
        th[t]=i;
        while(th[h]<=j) ++h;

        if(q[h]==0){
            putchar('0');
        }else {
            if(q[h]>0){
                flag = 0;
                tmp = q[h];
            }else {
                flag = 1;
                tmp = -q[h];
            }
            for(oNum=0;tmp>0;tmp/=10,++oNum)out[oNum]=tmp%10+'0';
            if(flag)putchar('-');
            for(--oNum;oNum>=0;--oNum)putchar(out[oNum]);
        }
        putchar((i==n)?'\n':' ');
    }
}

int main(){
    int i;
    int flag = 0;
    char ch;
    unsigned int tmp;
    while(scanf("%d %d",&n,&k)!=EOF){
        getchar();
        for(i=1;i<=n;++i){
            tmp = 0;
            flag = 0;
            ch=getchar();
            if(ch=='-')flag = 1;
            else tmp = ch-'0';
            while((ch=getchar())){
                if(!(ch>='0'&&ch<='9'))break;
                tmp = tmp*10+ch-'0';
            }
            if(flag)num[i] = -tmp;
            else num[i] = tmp;
        }
        min();
        max();
    }

    return 0;
}