滑动窗口 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();}}