题目
给定一个大小为 n≤106 的数组。
有一个大小为 k 的滑动窗口，它从数组的最左边移动到最右边。
你只能在窗口中看到 k 个数字。
每次滑动窗口向右移动一个位置。
以下是一个例子：
该数组为 [1 3 -1 -3 5 3 6 7]，k 为 3。
确定滑动窗口位于每个位置时，窗口中的最大值和最小值。
输入 数组长度和滑动区间长度 8 3 数组 1 3 -1 -3 5 3 6 7
输出 分别为区间最小和区间最大 -1 -3 -3 -3 3 3 3 3 5 5 6 7
public class 单调队列_滑动窗口 {
//初始化，为10的六次方的数据量，a为输入的数值存储，q为滑动区间并且存储的是下标不是值
public static int N = 1000010;
public static int[] a = new int[N], q = new int[N];
public static void main(String[] args) throws IOException {
//初始化
Scanner in = new Scanner(System.in);
PrintStream out = new PrintStream(System.out);
int n = in.nextInt(), k = in.nextInt();
for (int i = 0; ia[i] = in.nextInt();}
int hh = 0, tt = -1;
for (int i = 0; i
//推导：假设q[hh]=5, 那么什么时候会为True呢？
//也就是i-3+1 > 5, i大于7那么就至少为8，我们维护的区间最大为3，所以当i=8的时候，下标为5的这个元素不管怎样都是要被推出区间的
if (hh <= tt && i-k+1 > q[hh]) {hh++;}
//假如当前值小于区间尾部的值，那么就将尾部值移出区间，直到区间内没有值或者队尾值小于当前值为止，这样就保证了区间的头部永远为最小
while (hh <= tt && a[q[tt]] >= a[i]) {tt--;}
//插入当前值
q[++tt] = i;
//前两个数因为区间小于3，不输出，从第三个值开始输出队列头部
if (i >= k-1) {out.print(a[q[hh]] + " ");}
}
out.print("n");
//反模板，找窗口中的最大值
hh = 0;
tt = -1;
for (int i = 0; i
if (hh <= tt && i-k+1 > q[hh]) {hh++;}
//变动在这里，当a[i]大于区间尾部，将区间尾部移出区间，保证区间头部永远为最大
while (hh <= tt && a[q[tt]] <= a[i]) {tt--;}
q[++tt] = i;
if (i >= k-1) {out.print(a[q[hh]] + " ");}
}
}
}
ps：代码没AC，超时了，大家看个思路吧，BufferedReader和PrintWriter我都尝试了，还是不行，哎，java的痛苦呜呜呜，等我年底有空了把c学了，java就彻底不用了，python和c在手，谁还用java（笑
声明：算法思路来源为y总，详细请见https://www.acwing.com/
本文仅用作学习记录和交流
