#include
<
iostream
>
using
namespace
std;
int
N,k;
int
h,t;
int
num[
1000001
];
int
que[
1000001
];
int
ind[
1000001
];
void
init()
{
scanf(
"
%d%d
"
,
&
N,
&
k);
for
(
int
i
=
1
;i
<=
N;
++
i)
scanf(
"
%d
"
,
&
num[i]);
}
bool
empty()
{
if
(h
<=
t)
return
0
;
else
return
1
;
}
void
min_max(
int
flag)
{
h
=
1
; t
=
0
;
for
(
int
i
=
1
;i
<=
N;
++
i)
{
while
(i
-
ind[h]
+
1
>
k
&&!
empty()) h
++
;
//
保持k个
if
(flag)
while
(
!
empty()
&&
num[i]
<=
que[t]) t
--
;
else
while
(
!
empty()
&&
num[i]
>=
que[t]) t
--
;
//
删除不满足条件的队尾数值
que[
++
t]
=
num[i];
ind[t]
=
i;
if
(i
>=
k){
if
(i
>
k) printf(
"
"
);
printf(
"
%d
"
,que[h]);
}
}
printf(
"
\n
"
);
}
int
main()
{
init();
min_max(
1
);
min_max(
0
);
return
0
;
}
posted on 2009-06-27 23:38
xfstart07 阅读(266)
评论(0) 编辑 收藏 引用