窗口（单调队列）

窗口

题目描述：
给你一个长度为N的数组，一个长为K的滑动的窗体从最左移至最右端，你只能见到窗口的K个数，每次窗体向右移动一位，如下表：
Window position Min value
Max value
[ 1 3 -1 ] -3 5 3 6 7 ||-1 3
1 [ 3 -1 -3 ] 5 3 6 7 ||-3 3
1 3 [ -1 -3 5 ] 3 6 7 ||-3 5
1 3 -1 [ -3 5 3 ] 6 7 ||-3 5
1 3 -1 -3 [ 5 3 6 ] 7 ||3 6
1 3 -1 -3 5 [ 3 6 7 ] ||3 7
你的任务是找出窗口在各位置时的max value, min value.
输入描述：
第1行n,k,第2行为长度为n的数组
输出描述：
2行
第1行每个位置的min value
第2行每个位置的max value
样例输入：
8 3
1 3 -1 -3 5 3 6 7
样例输出：
-1 -3 -3 -3 3 3
3 3 5 5 6 7
数据范围及提示：
20%：n<=500;
50%: n<=100000;
100%: n<=1000000;
思路：
典型的单调队列
注意：开两个队列，一个维护最大值，另一个维护最小值，分别求出答案
千万不要图省事，用一个队列的头元素和尾元素来维护最大和最小，根据单调队列的性质，这样做是不正确的！

#include<iostream>
using namespace std;
const int maxn=1000010;
int n,m,a[maxn],q[maxn];
void find_min()
{
    int head=1,tail=0;
    for(int i=1;i<=n;i++)
    {
        while(head<=tail&&a[i]<a[q[tail]])
        tail--;
        q[++tail]=i;
        while(head<=tail&&q[head]<=i-m)
        head++;
        if(i>=m) cout<<a[q[head]]<<" ";
    }
    cout<<endl;
}
void find_max()
{
    int head=1,tail=0;
    for(int i=1;i<=n;i++)
    {
        while(head<=tail&&a[i]>a[q[tail]])
        tail--;
        q[++tail]=i;
        while(head<=tail&&q[head]<=i-m)
        head++;
        if(i>=m) cout<<a[q[head]]<<" ";
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    find_min();
    find_max();
    return 0;
}