AcWing 154. 滑动窗口
原题链接
简单
作者:
世界天光
,
2024-02-27 23:42:50
,
所有人可见
,
阅读 31
//窗口可以用队列进行维护,队首队尾插入与删除。
//这种题都是从暴力解的角度进行优化,例如本题暴力是先遍历每个数,以每个数为末尾遍历窗口值找到最小
//首先从队列的角度来看,根据本题窗口为3,所以队列最大长度只要3就可以。然后单调队列和单调栈类似的是,对于这个队列来说,在入队之前我们将入队数与队列中的数进行比较,我们容易看到,一旦队列中有数比入队数要大(我们这里用找最小值来说明),队列中大的数肯定不是最小值,所以将其出队排除。直到队列中剩余的数都比入队的数小或者队列中没有数时,将数入队。容易看出此时队列中的数是单增的。
//因为数组数据往往不是有序的,为了方便队列的管理,我们单调队列里存放对应数的下标
#include<iostream>
using namespace std;
const int N = 1000010;
int n, k;
int a[N],q[N];
int main()
{
cin.tie(0),cout.tie(0);
ios::sync_with_stdio(false);
cin >> n >> k;
for(int i = 0; i < n; i++) cin >> a[i];
int hh = 0, tt = -1;
for(int i = 0; i < n; i++)//遍历数组中的每个数
{
if(hh <= tt && q[hh] < i - k + 1) hh++;//首先队列非空,且队首元素下标如果在窗口以一个元素外,将其删掉,这里用if是因为每次窗口也就向右移动一格,所以队头最多出一个数
while(hh <= tt && a[q[tt]] >= a[i]) tt--;
q[++tt] = i;
if(i >= k-1) cout << a[q[hh]] << " ";//这个判断保证了窗口有三个元素时才会输出。
}
cout << endl;
//下面输出最大数同理
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]] << " ";//这个判断保证了窗口有三个元素时才会输出。
}
cout << endl;
return 0;
}