题目描述
给一个数组,然后来一个滑动窗口,窗口每次向右滑动1个,求每次滑动窗口中的最大值和最小值。
输入样例
8 3
1 3 -1 -3 5 3 6 7
输出样例
-1 -3 -3 -3 3 3
3 3 5 5 6 7
算法1
(暴力枚举) $O(n)$
思路:
1. 滑动窗口滑出的是队头,插入的是队尾,正好符合队列
2. 暴力:扫描数组,每次遍历滑动窗口的所有值,求出最大最小
3. 优化:发现当求窗口最小值的时候,当窗口元素是 -1 3 -2 的时候,-2 < 3 并且在3的后面,所以有-2在的窗口,3 永远不会出现,所以可以直接把它删除了,每次遍历数组的时候都这样删除,那么队列中存放的肯定是递增的,所以每次只需要取出队头即可。
4. 求最大值正好相反,当窗口元素是 4 -2 5 的时候,5>-2 并且在-2的后面,所以有5在的窗口,-2 永远不会出现,所以可以直接把它删除了,那么队列中存放的肯定是递增的,所以每次只需要取出队头即可。
时间复杂度:$O(n)$
参考文献:y总
Java 代码
import java.io.*;
public class Main {
static int N = 1000010;
static int[] a = new int[N];// 存储数组的值
static int[] q = new int[N];// 队列 存放数组的下标 模拟滑动窗口
static int hh = 0,tt = -1;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] str_01 = br.readLine().split(" ");
int n = Integer.parseInt(str_01[0]);
int k = Integer.parseInt(str_01[1]);
String[] str_02 = br.readLine().split(" ");
for (int i = 0; i < n; i++) a[i] = Integer.parseInt(str_02[i]);
// 处理最大值和最小值
for (int i = 0; i < n; i++){
// 保持队列的窗口大小等于滑动窗口的大小k
// i 终止坐标 i - k + 1 起始坐标
if (hh <= tt && i - k + 1 > q[hh]) hh++;
// 删除不必要的元素
// 如果队尾元素存放的下标对应的值 大于当前插入的值 说明队尾对应的值后面都不会用了
// 此时队列存放的a下标对应的值 是严格单调递增的
while (hh <= tt && a[q[tt]] >= a[i]) tt--;
// 插入当前值的下标
q[++tt] = i;
// 当 i >= k - 1 才会输出 只需要输出队头即可
if (i >= k -1) bw.write(a[q[hh]] + " ");
}
bw.write("\n");
// 处理最大值
for (int i = 0; i < n; i++){
if (hh <= tt && i - k + 1 > q[hh]) hh++;
while (hh <= tt && a[q[tt]] <= a[i]) tt--;
q[++tt] = i;
if (i >= k -1) bw.write(a[q[hh]] + " ");
}
bw.flush();
bw.close();
br.close();
}
}