之前好像学会过单调队列,但是我搜了一下,我的博客里面没有讲单调队列的。
今天突然发现我不会单调队列了,于是又重新学了一遍,现在好像又有一点学会了。
单调队列其实主要就是维护具有单调性的子序列。
拿这个题的样例模拟一下单调队列的过程:q表示元素序列,p表示下标序列,序列从下标1开始。
1 3 -1 -3 5 3 6 7
round 1: q{1}, p{1}
round 2: q{1,3},p{1,2}
round 3: q{-1}, p{3}
round 4: q{-3}, p{4}
round 5: q{-3,5}, p{4,5}
round 6: q{-3,3}, p{4,6}
round 7:q{-3,3,6}, p{4,6,7}
round 8: q{3,6,7}, p{6,7,8} //k=3, 只保留最新的3个,所以把之前的-3删除了。
由于维护的是单调增队列,故求最小值的时候,答案就是队首元素。
很简单吧。
直接看代码:
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
const int maxn = 1e6+7;
const int INF = 0x3f3f3f3f;
int a[maxn];
deque<int> mnq,mxq;
int main()
{
int n,k;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",a+i);
for(int i=1;i<=n;i++)
{
while(!mnq.empty() && a[mnq.back()]>=a[i]) mnq.pop_back();
mnq.push_back(i);
while(mnq.front()<=i-k) mnq.pop_front();
if(i>=k) printf("%d ",a[mnq.front()]);
}
printf("\n");
for(int i=1;i<=n;i++)
{
while(!mxq.empty() && a[mxq.back()]<=a[i]) mxq.pop_back();
mxq.push_back(i);
while(mxq.front()<=i-k) mxq.pop_front();
if(i>=k) printf("%d ",a[mxq.front()]);
}
printf("\n");
return 0;
}