910. 单调队列
时间限制：1000 MS 内存限制：512 MB
题目描述
# 单调队列 ## 题目描述 给定一个长度为 $n$ 的整数序列 $a$ 和一个大小为 $k$ 的窗口。 窗口最初覆盖序列的前 $k$ 个元素，随后每次向右移动一个位置，直到窗口覆盖序列的最后 $k$ 个元素。 请按窗口从左到右的顺序，求出每个完整窗口中元素的最小值和最大值。共有 $n-k+1$ 个完整窗口，第 $i$ 个窗口覆盖 $a_i,a_{i+1},\ldots,a_{i+k-1}$。 例如，当序列为 $[1,3,-1,-3,5,3,6,7]$、$k=3$ 时，各窗口的最小值和最大值如下： | 窗口中的元素 | 最小值 | 最大值 | | --- | --- | --- | | $[1,3,-1]$ | $-1$ | $3$ | | $[3,-1,-3]$ | $-3$ | $3$ | | $[-1,-3,5]$ | $-3$ | $5$ | | $[-3,5,3]$ | $-3$ | $5$ | | $[5,3,6]$ | $3$ | $6$ | | $[3,6,7]$ | $3$ | $7$ | ## 输入格式 从文件 `window.in` 读入数据。 输入共两行。 第一行包含两个正整数 $n,k$，分别表示序列的长度和窗口的大小。 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示给定的序列。 ## 输出格式 输出到文件 `window.out`。 输出共两行，每行包含 $n-k+1$ 个整数，相邻整数之间用空格分隔。 第一行按窗口从左到右的顺序，输出各完整窗口的最小值。 第二行按窗口从左到右的顺序，输出各完整窗口的最大值。 ## 数据范围 - 对于 $50\%$ 的数据，$1\le n\le 10^5$。 - 对于 $100\%$ 的数据，$1\le k\le n\le 10^6$。 - 所有 $a_i$ 均为整数，且 $-2^{31}\le a_i<2^{31}$。 ## 样例输入 ``` 8 3 1 3 -1 -3 5 3 6 7 ``` ## 样例输出 ``` -1 -3 -3 -3 3 3 3 3 5 5 6 7 ``` ## 时间与内存限制 - 时间限制：$1000$ 毫秒。 - 内存限制：$512$ MB。