问题1768--滑动窗口（POJ2823）

1768: 滑动窗口（POJ2823）

时间限制: 1 Sec  内存限制: 128 MB
提交: 21  解决: 16
[提交] [状态] [讨论版] [命题人:]

题目描述

有n（n≤106)个元素的数组，以及一个大小为k的滑动窗口，将滑动窗口从数组的最左边移动到最右边，只可以在该窗口中看到k个数字，滑动窗口每次都向右移动一个位置，请确定滑动窗口在每个位置的最大值和最小值。下面是一个例子，数组是[1 3 -1 -3 5 3 6 7]，k是3。
 


输入

第1行包含整数n和k，表示元素个数和滑动窗口的长度；第2行包含n个整数。

输出

第1行从左到右分别输出每个窗口中的最小值，第2行输出最大值。

样例输入 Copy 

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

样例输出 Copy 

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

提示

POJ2823

来源/分类

动态规划算法 单调队列 
[提交] [状态]