滑动窗口

题意

求长度为的窗口的最大值和最小值。

分析

单调队列入门题，也是很好的入门题。

用单调队列来解决问题，一般都是需要得到当前的某个范围内的最小值或最大值。

假设我们要求最小值，我现在有一个队列，我让他里面的值升序排列，类似于，现在我又新加进来一个，那么他会把排在他前面的比他大的数踢掉，就变成了。

我们可以得出队列里面的值的下标一定是递增的，因为是按顺序加进去的，然后当队首和当前位置相差很远的时候，也把队首踢掉

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define int long long
const int inf = 0x3f3f3f3f;
const int maxn = 1001110;
const int M = 1e9+7;
int n,m,k,ok;

int a[maxn];

int q[maxn];

signed main()
{   
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    for(int i = 1; i <= n; i++) 
    {
        cin>>a[i];
    }
    int h = 1,r = 0;
    for(int i = 1; i <= n; i++)             //处理最小值
    {   
        while(h <= r && i >= q[h]+k) h++;
        while(h <= r && a[q[r]] >= a[i]) r--;
        q[++r] = i;
        if(i >= k) cout<<a[q[h]]<<' ';
    }
    cout<<endl;
    h = 1,r = 0;
    for(int i = 1; i <= n; i++)         //处理最大值
    {
        while(h <= r && i >= q[h]+k) h++;
        while(h <= r && a[q[r]] <= a[i]) r--;
        q[++r] = i;
        if(i >= k) cout<<a[q[h]]<<' ';
    }
    cout<<endl;
    return 0;
}