吴耀坤 @ 2019-06-07 15:15:02
#include<cstdio>
#include<deque>
#define MP make_pair
using namespace std;
deque<pair<int ,int> >q;
int n,a[200000],w;
int main()
{
scanf("%d%d",&n,&w);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
{
while(!q.empty()&&i-q.front().first>=w) q.pop_front();
while(!q.empty()&&q.back().second>=a[i]) q.pop_back();
q.push_back(MP(i,a[i]));
if(i>=w) printf("%d ",q.front().second);
}
printf("\n");
q.clear();
for(int i=1;i<=n;i++)
{
while(!q.empty()&&i-q.front().first>=w) q.pop_front();
while(!q.empty()&&q.back().second<=a[i]) q.pop_back();
q.push_back(MP(i,a[i]));
if(i>=w) printf("%d ",q.front().second);
}
}
by presucc @ 2019-06-07 15:18:18
@吴耀坤 数据范围 10^6,您的数组只有2*10^5
by 吴耀坤 @ 2019-06-16 15:04:57
@LZCR 非常感谢