滑动窗口

这题滑动窗口，首先我那道题，发现是个区间最大值和最小值。很显然，可以用线段树和树状数组或者ST表去强行区间查询。

很不幸，牛客把内存卡的死死的，因为这题我在POJ 2823上做过，那里内存不严格，所以我线段树一发就过了。

这里线段树只能拿70f分。

滑动窗口是个经典的单调队列的题目，本题要求最大值和最小值，是维护2个单调队列，一个单调递减队列，队列头是保证对大值，一个是单调递增队列，保证队头最小值。

那么，我们如何去维护他呢？？

这里我们以单调递减队列为例。

首先我们要知道，每次算区间的时候，整个区间k相当于移动了一格。那么我们没必要重新去计算。 我们每次去计算的时候，先判断下，队列顶的元素是不是超出我们的区间范围了，如果超出了，那么pop掉，因为超出区间范围，我们没必要算他了。如果当前元素大于队列顶部的那个元素，我们需要把队列顶部的那个元素弹出，因为后面最大值将不会是他了。判断好上面的情况后，我们需要把这个元素加到队列尾部，但是加的时候，我们需要去判断当前元素是不是大于尾部元素，如果大于尾部元素，也pop掉。我们实时维护的是队头最大值，这点要牢记。 这是最大值的做法，最小值也雷同，只要改变大于符号为小于符号即可。

题解大佬用了数组来模拟，我是用双端队列deque来模拟的。

#include <bits/stdc++.h>

using namespace std;

const int N=1e6+100;

int n,k;

struct Node
{
    int val;
    int pos;
}a[N];

deque<Node>dq;//计算最大值
deque<Node>dq2;//计算最小值 
int x[N];
int y[N];

void solve()
{
    for(int i=1;i<=n;i++)
    {
        if(dq.empty())
        {//如果是空的,直接加入 
            dq.push_back(a[i]); 
        }
        else
        {
            Node top=dq.front();//访问头结点
            if(i-top.pos>=k)
            {
                dq.pop_front();
            }//如果超出区间直接删掉
            if(a[i].val>dq.front().val)
            {
                dq.pop_front();
            } 
            while(!dq.empty()&&a[i].val>dq.back().val)
            {
                dq.pop_back();
            }
            dq.push_back(a[i]); 
        } 
        x[i]=dq.front().val;
    }

    for(int i=1;i<=n;i++)
    {
        if(dq2.empty())
        {//如果是空的,直接加入 
            dq2.push_back(a[i]); 
        }
        else
        {
            Node top=dq2.front();//访问头结点
            if(i-top.pos>=k)
            {
                dq2.pop_front();
            }//如果超出区间直接删掉
            if(a[i].val<dq2.front().val)
            {
                dq2.pop_front();
            } 
            while(!dq2.empty()&&a[i].val<dq2.back().val)
            {
                dq2.pop_back();
            }
            dq2.push_back(a[i]); 
        } 
        y[i]=dq2.front().val;
    }
}

int main()
{
    scanf("%d%d",&n,&k);

    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i].val);
        a[i].pos=i;
    }

    solve();

    for(int i=k;i<=n;i++)
    {
        printf("%d%c",y[i],i==n?'\n':' '); 
    }

    for(int i=k;i<=n;i++)
    {
        printf("%d%c",x[i],i==n?'\n':' '); 
    } 
    return 0;
}