之前只系统学习过单调栈,以为单调队列和单调栈差不多,就没学。结果做到一道单调队列的题时,发现自己根本写不出来(高估自己了。。。。)
这是牛客每日一题中的,原题链接:https://ac.nowcoder.com/acm/problem/50528
单调队列:不断地向缓存数组里读入元素,也不时地去掉最老的元素,不定期的询问当前缓存数组里的最小\大的元素。
这道题就是单调队列的模板题
直接上代码:
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int Size=1000005;
int a[Size],qmax[Size],qmin[Size],savemax[Size],savemin[Size];
int main()
{
int n,k,cnt=1;
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++)
{scanf("%d",&a[i]);}
int beg=1,top=0;//qmax队列的队首指针和队尾指针
int st=1,ed=0;//qmin队列的队首指针和队尾指针
for(int i=1;i<=n;i++)
{
while(beg<=top&&a[i]>=a[qmax[top]])
{top--;}
qmax[++top]=i;
while(st<=ed&&a[i]<=a[qmin[ed]])
{ed--;}
qmin[++ed]=i;
if(i>=k)
{
while(qmax[beg]<=i-k)beg++;
while(qmin[st]<=i-k)st++;
savemax[cnt]=a[qmax[beg]];
savemin[cnt]=a[qmin[st]];
cnt++;
}
}
for(int i=1;i<cnt;i++)
{printf("%d ",savemin[i]);}
printf("\n");
for(int i=1;i<cnt;i++)
{printf("%d ",savemax[i]);}
printf("\n");
return 0;
}
123