滑动窗口（c++）（数组模拟队列）

解题思路:  构造单调队列 答案即为队头

注意事项:  队列存放数组下标  用scanf和printf更快

参考代码:

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1000010;
int a[N],q[N];
int hh,tt;
int main(void)
{
//初始化队头和队尾
    hh=0;
    tt=-1;
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)
    scanf("%d",&a[i]);
    for(int i=0;i<n;i++)
    {
      //判断队头是否已经划出窗口
        if(hh<=tt&&i+1-k>q[hh])  // i-k+1为范围内队头坐标  若大于实际队头坐标则已超出窗口
        hh++;
      //若队内元素大于要存放的a[i] 则tt--，舍弃，  保证队内坐标对应元素为单调  
        while(hh<=tt&&a[q[tt]]>=a[i])
        tt--;
        //插入元素对应坐标
        q[++tt]=i;
        
        if(i+1>=k)
        printf("%d ",a[q[hh]]);
    }
    puts(" ");
    //同上
    hh=0,tt=-1;
        for(int i=0;i<n;i++)
    {
        if(hh<=tt&&i+1-k>q[hh])
        hh++;
        while(hh<=tt&&a[q[tt]]<=a[i])
        tt--;
        q[++tt]=i;
        if(i+1>=k)
        printf("%d ",a[q[hh]]);
    }
    puts(" ");
    return 0;
}