滑动窗口 AcWing （JAVA）

 给定一个大小为 n≤10^6 的数组。

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

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

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

以下是一个例子：

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

窗口位置	最小值	最大值
[1 3 -1] -3 5 3 6 7	-1	3
1 [3 -1 -3] 5 3 6 7	-3	3
1 3 [-1 -3 5] 3 6 7	-3	5
1 3 -1 [-3 5 3] 6 7	-3	5
1 3 -1 -3 [5 3 6] 7	3	6
1 3 -1 -3 5 [3 6 7]	3	7

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

输入格式:

 输入包含两行。

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

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

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

输出格式:

输出包含两个。

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

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

解题思路： 如果朴素的做法，将每次得到的窗口进行遍历找最小值。时间复杂度大概是nk，不出意外是会超时的。如何对其进行优化呢？

首先以数组q[N]，作为本题队列，a[N]存入输入的元素。我们知道下标和元素具有一 一对应的关系，所以q[i]不是存入元素所对应的值，而是元素所对应的下标。

 在这里设hh = 0为头指针，tt = - 1为尾指。

首先应该明确窗口的特点：即内部元素的数量在k的时候即可输出最内部最小值和最大值。此后每移动一下就再次输出一次。这恰好哦可以用循环变量i来表示,如下窗口：

[a,b,c,d.....]

0                i             窗口内部元素的数量可用 （i - 0 + 1）来表示，当窗口内数量够k个的时候即可输出，即i - 0 + 1 >= k即 i >= k - 1。

有趣的是当 0~i + 2 中c为最小值的时候，当窗口向右边移动的时候：

[b,c,d,e.....]

1               i + 1         min = c

[c,d,e,f.....]

2              i + 2          min = c

不难看出窗口在移动的时候，最小值仍是c,如果能用队列存入最小值的下标(即q[tt] = 2),那就避免重新遍历窗口的麻烦。那问题来了设立队列只是为了存入一个最小值的吗?这显然不是，如下窗口继续向右移动：

[d,e,f,g.....]

3             i + 3       min =  ?    由此可见如果队列里值只存入c的下标,当窗口不包含c的时候队列内的 q[tt] = 2 也就没用了。

那么需要队列，理想的情况是让队列内存入 最小元素下标，第二小元素下标，第三小元素下标.......

当窗口不再包含最小元素的时候那么就可以在队列内删去了，那么第二小元素就理应成为新的最小元素了，以此类推，队列头部元素一直是符合条件的最小元素下标。

至于如何输出最大值，和上述反着来即可。

理论成立代码如下（未加速版）：

import java.util.*;public class Main {public static int N = 1000010;public static void main(String[] args) {Scanner sc  = new Scanner(System.in);int a[] = new int [N];//数组int q[] = new int [N];//队列int n = sc.nextInt();int k = sc.nextInt();for(int i = 0; i < n; i ++) a[i] = sc.nextInt();int hh = 0, tt = -1;//队头，队尾，q[hh]存入最小元素下标for(int i = 0; i < n; i ++) {//找最小值if(hh <= tt && q[hh] < i - k + 1) hh ++;//在滑动窗口的外面，移动左窗口while(hh <= tt && a[q[tt]] >=a[i]) tt--;//队尾不比添加进来的数小，那就没用，删掉。q[++ tt] = i;//添加元素。if(i >= k - 1) {if(i == n-1)System.out.println(a[q[hh]]);elseSystem.out.print(a[q[hh]]+" ");  }	    }
//输出最大值hh = 0; tt = -1;for(int i = 0; i < n; i ++) {if(hh <= tt && q[hh] < i - k + 1 ) hh ++;while(hh <= tt && a[q[tt]] <= a[i]) tt --;q[++ tt] = i;if(i >= k - 1) {if(i == n - 1)System.out.print(a[q[hh]]);elseSystem.out.print(a[q[hh]]+" ");}}}
}

由于最后一个数据过于庞大，时间超时了，想通过，得用如下的加速版：

import java.io.*;
import java.util.*;;
public class Main {public static int N = 1000010;public static void main(String[] args) throws IOException {// TODO Auto-generated method stubScanner sc = new Scanner(new BufferedInputStream(System.in));BufferedWriter sout = new BufferedWriter(new OutputStreamWriter(System.out));int a[] = new int [N];//数组int q[] = new int [N];//队列int n = sc.nextInt();int k = sc.nextInt();for(int i = 0; i < n; i ++) a[i] = sc.nextInt();int hh = 0, tt = -1;//队头，队尾，q[hh]存入最小元素下标for(int i = 0; i < n; i ++) {//找最小值if(hh <= tt && q[hh] < i - k + 1) hh ++;//在滑动窗口的外面，移动左窗口while(hh <= tt && a[q[tt]] >=a[i]) tt--;//队尾不比添加进来的数小，那就没用，删掉。q[++ tt] = i;//添加元素。if(i >= k - 1) {sout.write(a[q[hh]]+" ");  }	    }sout.write("\n");//输出最大值hh = 0; tt = -1;for(int i = 0; i < n; i ++) {if(hh <= tt && q[hh] < i - k + 1 ) hh ++;while(hh <= tt && a[q[tt]] <= a[i]) tt --;q[++ tt] = i;if(i >= k - 1) {sout.write(a[q[hh]]+" ");}}sout.close();sc.close();}}