AcWing 154. 滑动窗口 详细注释
原题链接
简单
# include <iostream>
using namespace std;
const int N = 1000010;
int n,k;
int a[N],q[N];
//q代表窗口中的数字
int main()
{
cin.tie(0);
cout.tie(0);
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&&i-k+1>q[hh]) hh++;
//如果接下来入队的数字小于队尾数字,那么最小值就一定是该数字
//那么窗口中的数字为了节省空间就可以删除,即 将队尾向前移动
//直到遇到队内比该数字更小的数字,如果没有则该数字将成为队中队尾数字
//同时也是最小的数字,该操作是为了确保队列中的队头始终为队中最小的数字
while(hh<=tt&&a[q[tt]]>=a[i]) tt--;
q[++tt]=i;
//增加一个判断条件,当窗口完整后在开始输出
if(i>=k-1) cout << a[q[hh]]<<" ";
}
puts("");
hh=0,tt=-1;
for(int i=0;i<n;i++)
{
if(hh<=tt&&i-k+1>q[hh]) hh++;
while(hh<=tt&&a[q[tt]]<=a[i]) tt--;
q[++tt]=i;
if(i>=k-1) cout << a[q[hh]]<<" ";
}
return 0;
}~