題目 2500:
信息學(xué)奧賽一本通T1597-滑動窗口
時間限制: 2s
內(nèi)存限制: 192MB 提交: 359 解決: 78
題目描述
原題來自：POJ 2823
給一個長度為 N 的數(shù)組，一個長為 K 的滑動窗體從最左端移至最右端，你只能看到窗口中的 K 個數(shù)，每次窗體向右移動一位，如下圖：
你的任務(wù)是找出窗體在各個位置時的最大值和最小值。
輸入格式
第 1 行：兩個整數(shù) N 和 K；
第 2 行：N 個整數(shù)，表示數(shù)組的 N 個元素(≤2×109 )；
第 2 行：N 個整數(shù)，表示數(shù)組的 N 個元素(≤2×109 )；
輸出格式
第一行為滑動窗口從左向右移動到每個位置時的最小值，每個數(shù)之間用一個空格分開；
第二行為滑動窗口從左向右移動到每個位置時的最大值，每個數(shù)之間用一個空格分開。
第二行為滑動窗口從左向右移動到每個位置時的最大值，每個數(shù)之間用一個空格分開。
樣例輸入
8 3 1 3 -1 -3 5 3 6 7
樣例輸出
-1 -3 -3 -3 3 3 3 3 5 5 6 7
提示
數(shù)據(jù)范圍與提示：
對于 20% 的數(shù)據(jù)，K≤N≤1000；
對于 50% 的數(shù)據(jù)，K≤N≤105 ；
對于 100% 的數(shù)據(jù)，K≤N≤106 。
對于 20% 的數(shù)據(jù)，K≤N≤1000；
對于 50% 的數(shù)據(jù)，K≤N≤105 ；
對于 100% 的數(shù)據(jù)，K≤N≤106 。