滑动窗口

Grade 100 Open Time Thursday, 4 June 2020, 10:15 PM
Discount 0.8 Time Discount Thursday, 4 June 2020, 10:15 PM
Allow late Yes Close Time Thursday, 4 June 2020, 10:15 PM
Input file sliding.in Output file sliding.out

【题目描述】滑动窗口(sliding)POJ 2823

有一个长度为k的滑动窗口从数组的左端滑到右端,试输出窗口每次移动时窗口里能看到的最大值和最小值。例如有数组为{1,3,-1,-3,5,3,6,7},窗口长度为3,则输出的最大最小值如表3.2所示。

表3.2

窗口位置

最小值

最大

【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

 

【输入格式】

第一行为两个整数,即n和k(1<n≤1 000 000)。

第二行为n个整数。

【输出格式】

第一行为最小数(行末均有一空格),第二行为最大数(行末无空格有换行)。

【输入样例】

8 3

1 3 -1 -3 5 3 6 7

【输出样例】

-1 -3 -3 -3 3 3

3 3 5 5 6 7