#65. 滑动窗口

滑动窗口

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个大小为n106\red{n≤10^6}的数组。

有一个大小为k\red{k}的滑动窗口,它从数组的最左边移动到最右边。

您只能在窗口中看到k\red{k}个数字,1<=k<=n\red{ 1 <= k <= n}

每次滑动窗口向右移动一个位置。

以下是一个例子:

该数组为[1 3 1 3 5 3 6 7]\red{[1~3 ~-1~ -3~5~3~6~7]}k\red{k}3\red{3}

窗口位置 最小值 最大值
[1 3 1] 3 5 3 6 7\red{[1~3~ -1] ~-3~ 5~ 3~ 6~ 7} 1\red{-1} 3\red{ 3}
1 [3 1 3] 5 3 6 7\red{1~ [3 ~-1~ -3]~ 5 ~3 ~6 ~7} 3\red{-3}
1 3 [1 3 5] 3 6 7\red{1 ~3~ [-1~ -3~ 5]~ 3 ~6 ~7} 5\red{ 5}
1 3 1 [3 5 3] 6 7\red{1 ~3~ -1 ~[-3~ 5 ~3]~ 6 ~7}
1 3 1 3 [5 3 6] 7\red{1 ~3~ -1 ~-3 ~[5 ~3 ~6]~ 7} 3\red{3 } 6\red{ 6}
1 3 1 3 5 [3 6 7]\red{1 ~3~ -1~ -3~ 5~ [3~ 6~ 7]} 7\red{ 7}

您的任务是确定滑动窗口位于每个位置时,窗口中的最大值和最小值。

输入格式

输入包含两行。

第一行包含两个整数n\red{n}k\red{k},分别代表数组长度和滑动窗口的长度。

第二行有n\red{n}个整数,代表数组的具体数值。

同行数据之间用空格隔开。

输出格式

输出包含两个。

第一行输出,从左至右,每个位置滑动窗口中的最小值。

第二行输出,从左至右,每个位置滑动窗口中的最大值。

样例

输入样例

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

输出样例

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

少年宫端午练习

未参加
状态
已结束
规则
OI
题目
5
开始于
2022-6-4 14:30
结束于
2022-6-4 17:30
持续时间
3 小时
主持人
参赛人数
31