单调队列

Problem Description

有一个长为 n 的序列 a，以及一个大小为 k 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

Analysis of ideas

滑动窗口
比如说我们求一个区间的最小值,这个时候来了一个最小的,那么前面保存的信息都没有任何意义了,就可以把前面的信息给舍弃
也就是我们说的单调队列

Accepted code

#include <bits/stdc++.h>
using namespace std;
int n,k;

int a[maxn];

int q[maxn];        //队列存下标,每次从队尾进来,把前面比他小的都踢出去
int head,rear;      //head <= rear 保证队列不为空

signed main()
{
    cin>>n>>k;
    for(int i = 1; i <= n; i++) 
    {
        cin>>a[i];
    }
    head = 1,rear = 0;
    for(int i = 1; i <= n; i++) 
    {   
        while(head <= rear && q[head]+k <= i) head++;
        while(head <= rear && a[i] <= a[q[rear]]) rear--;
        q[++rear] = i;
        if(i >= k) cout<<a[q[head]]<<' ';
    }
    cout<<endl;
    head = 1, rear = 0;
    for(int i = 1; i <= n; i++) 
    {
        while(head <= rear && q[head]+k <= i) head++;
        while(head <= rear && a[i] >= a[q[rear]]) rear--;
        q[++rear] = i;
        if(i >= k) cout<<a[q[head]]<<' ';
    }
    cout<<endl;
    return 0;
}