本文共 2479 字，大约阅读时间需要 8 分钟。

给定一个大小为n≤106n≤106的数组。

有一个大小为k的滑动窗口，它从数组的最左边移动到最右边。

您只能在窗口中看到k个数字。

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

以下是一个例子：

该数组为[1 3 -1 -3 5 3 6 7]，k为3。

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

输入格式

输入包含两行。

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

第二行有n个整数，代表数组的具体数值。

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

输出格式

输出包含两个。

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

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

输入样例：

8 31 3 -1 -3 5 3 6 7

输出样例：

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

思想：

1、暴力解法

外层循环整个数组，内层循环当前节点下前k个下标，找到最小值输出即可；时间复杂度O(kn)

伪代码：

for(i = 0; i < n;++i){外层循环整个数组

for(j = i - k + 1; j < =i; ++j)内层循环区间【i - k + 1, i]】比较找到最小值

}

2、单调队列优化（单调递增），原则保证队头是最小的依单调递增，每次加入队列前要与队尾比较（小于队尾，则出队），因为队尾是队列中最大的

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

       -1     -3     -3    -3    3    3

观察上图【】表示队列元素

思想：

队空，1 进队列【1】；

3比1小，3进队列【1,3】；

-1比3小，3出队【1】，继续比，我们要保证单调性，-1比1小，1出队【】，队空，当前元素入队【-1】；坐标大于等于k，输出队头-1

-3比-1小，-1出队，队空-3入队【-3】 输出队头-3；

5比-3大，5入队【-3,5】输出队头-3；

3比5小，5出队，3比-3大，3入队【-3,3】输出队头-3

此时-3的坐标是3,6的坐标是6，不再区间[4，6]内，因此队头出队【3】，6与3大，6入队，输出队头3

7比6大，7入队【3,6,7】输出队头3

结果是

-1 -3 -3 -3 3 3

同理最大值也是构造单调队列（单调递减）

import java.io.*;import java.lang.Integer;class Main{    static int N = 1000010;//>10^6    static int[] q = new int[N], p = new int[N];    public static void main(String[] args)throws Exception{        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));        BufferedWriter buw = new BufferedWriter(new OutputStreamWriter(System.out));        String[] params = buf.readLine().split(" ");        int n = Integer.valueOf(params[0]);        int k = Integer.valueOf(params[1]);        String[] nums = buf.readLine().split(" ");        int hh = 0, tt = -1;        for(int i = 0; i < n; ++i){            p[i] = Integer.valueOf(nums[i]);        }        for(int i = 0; i < n; ++i){            if(hh <= tt && i - k + 1 > q[hh])hh++;//保证滑动窗口的大小为k，i - k + 1计算得到队头下标与队头下标q[hh]比较，如果大于队头则加1            while(hh <= tt && p[i] < p[q[tt]])tt--;//剔除单调队列前面大的，直到遇到比自己小的            q[++tt] = i;            if(hh <= tt && i >= (k - 1))buw.write(p[q[hh]] + " ");        }        buw.write("\n");//换行        buw.flush();        hh = 0; tt = -1;        for(int i = 0; i < n; ++i){            if(hh <= tt && i - k + 1 > q[hh])hh++;//保证滑动窗口的大小为k，大于k则队头后移            while(hh <= tt && p[i] > p[q[tt]])tt--;//剔除单调队列前面小的，直到遇到比自己大的的            q[++tt] = i;            if(hh <= tt && i >= (k - 1))buw.write(p[q[hh]] + " ");        }        buw.flush();        buf.close();        buw.close();    }}