_Glassy_Sky_ @ 2023-01-13 21:24:46
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
struct node
{
int num, id;
}que[maxn];
int head = 1, tail = 0;
int a[maxn];
int main()
{
int n, k;
cin >> n >> k;
for(int i = 1; i <= n; i ++)
cin >> a[i];
for(int i = 1; i <= n; i ++)
{
while(head <= tail && que[head].id + k > i)
head ++;
while(head <= tail && que[tail].num > a[i])
tail --;
que[++ tail].id = i;
que[tail].num = a[i];
if(i >= k)
printf("%d ", que[head].num);
}
head = 1, tail = 0;
cout << "\n";
for(int i = 1; i <= n; i ++)
{
while(head <= tail && que[head].id + k <= i)
head ++;
while(head <= tail && que[tail].num <= a[i])
tail --;
que[++ tail].id = i;
que[tail].num = a[i];
if(i >= k)
printf("%d ", que[head].num);
}
return 0;
}
by _l_l_ @ 2023-01-13 21:40:38
@FZwangmuem 第一次单调队列的第一个 while 第二个判断条件是 <=
号
by _Glassy_Sky_ @ 2023-01-14 14:08:14
@_ll 谢谢大佬,已经过了