…
include [HTML_REMOVED]
include [HTML_REMOVED]
include [HTML_REMOVED]
using namespace std;
const int N = 1000010;
// 分别表示原数组 和 队列
int a[N],q[N];
int n,k;
int hh ,tt;
int main()
{
cin>>n>>k;
for(int i=0;i[HTML_REMOVED]>a[i];
hh = 0, tt = -1;
for(int i=0;i<n;i++)
{
if(hh<=tt && i-k+1 > q[hh]) hh++;
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]]<<" ";
}
return 0;
}
…