题目描述

滑动窗口

用数组模拟队列

按顺序，先进的作为队首

队列中在队首插入，在队尾提出（右边是队首，左边是队尾）

队列中的数从队尾依次与队首比较，

C++ 代码

#include<iostream>
using namespace std;
const int N=1000010;
int n,k;
int a[N],q[N];      //a[N]表示原数组,q[N]表示队列数组,存储原数组数字的下标（因为在比较过程中会删去较大的数）
int main()
{
    cin>>n>>k;
    for(int i=0;i<n;i++) cin>>a[i];      //输入原数组

    //输出每个滑动窗口的最小值，即删去每个队列中的较大数
    int hh=0,tt=-1;       //hh为队头，标记留下来的第一个数，tt为队尾，标记刚进来的数

    for(int i=0;i<n;i++)
    {
        if(hh<=tt&&q[hh]<i-k+1)hh++;         //判断队头是否不在队列首位中，若不在则继续向前移动


      //如果队首队尾重合、左右颠倒且当前队尾的数大于新加入队首的数，则这个数从队列中排除，向队首靠近继续比较

        //插入新的数字之前先判断队尾元素是否大于当前元素
        while(hh<=tt&&a[q[tt]]>=a[i])tt--;   //删去大于队头的数

        //将当前数的下标存入队列中
        q[++tt]=i;

        //最后得到的数列单调递增，则此时队头的元素为最大值
        if(i>=k-1)cout<<a[q[hh]]<<" ";
    }
    puts("");//向标准输出设备（屏幕）输出字符串并换行，将'\0'转换为回车换行


    //同理，对称
    hh=0,tt=-1;
    for(int i=0;i<n;i++)
    {
        if(hh<=tt&&q[hh]<i-k+1)hh++;
        while(hh<=tt&&a[q[tt]]<=a[i])tt--;
        q[++tt]=i;
        if(i>=k-1)cout<<a[q[hh]]<<" ";
    }
    puts("");
    return 0;
}