UOJ Logo LFYZ Online Judge

LFYZOJ

#326. 滑动的窗户(window)

统计

问题描述

在一个包含 $n$ 个元素的数组上,有一个长度为 $k$ 的窗户在从左向右滑动。窗户每滑动到一个位置,我们都可以看到 $k$ 个元素在窗户中。如下的例子所示,假设数组为 [1 3 -1 -3 5 3 6 7],而 $k$ 等于 $3$:

窗户位置                        最小值        最大值
[1  3  -1] -3  5  3  6  7        -1            3
1 [3  -1  -3]  5  3  6  7        -3            3
1  3 [-1  -3  5]  3  6  7        -3            5
1  3  -1 [-3  5  3]  6  7        -3            5
1  3  -1  -3 [5  3  6]  7         3            6
1  3  -1  -3  5 [3  6  7]         3            7

对于窗户滑动过的每个位置,请给出窗户内 $k$ 个元素的最小值和最大值。

输入格式

输入的第一行包括两个整数 $n$,$k$,$n$ 表示数组的长度,$k$ 表示窗户的长度。

接下来一行包括 $n$ 个整数,表示这个 $n$ 个元素的数组。

输出格式

输出包含两行,每行包括 $n-k+1$ 个整数,第一行表示窗户从左到右滑动过程中的最小值,第二行表示窗户从左到右滑动过程中的最大值。

样例一

input

8 3
1 3 -1 -3 5 3 6 7

output

-1 -3 -3 -3 3 3
3 3 5 5 6 7

数据范围与约定

对于 $100\%$ 的数据,$3 \leq n \leq 1000000, 1\leq k \leq n$,数组中的每个元素均在int范围内。

时间限制: $3\mathrm{s}$

内存限制: $256\mathrm{MB}$