【单调队列】POJ 2823 Sliding Window

求 连续的K个元素中的最小值和最大值

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <cmath>
using namespace std;
#include <queue>
#include <stack>
#include <vector>
#include <deque>
#define cler(arr, val)    memset(arr, val, sizeof(arr))
typedef long long  LL;
const int MAXN = 1002000;
const int MAXM = 6000010;
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
int a[MAXN],q[MAXN];
int n,k;
void getnum1()//取最小
{
    int l=1,r=0;//l
    cler(q,0);
    q[1]=1;
    for(int i=1;i<=n;i++)
    {
        if(i-q[l]==k) l++;
        if(a[q[r]]<a[i]||r==l-1)//将第i个放进队尾
            q[++r]=i;
        else//更新队尾的元素 一直到比第i个还要小
        {
            while(r>=l&&a[i]<=a[q[r]])
                q[r--]=i;
            r++;
        }
        if(i>=k)printf("%d ",a[q[l]]);
    }
    puts("");
}
void getnum2()
{
    int l=1,r=0;
    cler(q,0);
    q[1]=1;
    for(int i=1;i<=n;i++)
    {
        if(i-q[l]==k) l++;
        if(a[q[r]]>a[i]||r==l-1)
            q[++r]=i;
        else
        {
            while(r>=l&&a[i]>=a[q[r]])
                q[r--]=i;
            r++;
        }
        if(i>=k)printf("%d ",a[q[l]]);
    }
    puts("");
}
int main()
{

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
#endif
    while(cin>>n>>k)
    {
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        getnum1();
        getnum2();
    }
    return 0;
}