单调队列

定义

顾名思义，队列中的元素是单调的，要么递增要么递减
使用Java中的Deque

重点

动态地保证队列中元素有序！！！
作用就是找到当前元素x左边固定窗口内第一个大于/小于x的第一个元素y

例题

AcWing 154. 滑动窗口
给定一个大小为 n≤106 的数组。
有一个大小为 k 的滑动窗口，它从数组的最左边移动到最右边。
你只能在窗口中看到 k 个数字。
每次滑动窗口向右移动一个位置。
以下是一个例子：
该数组为 [1 3 -1 -3 5 3 6 7]，kk 为 3。

你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。
输入格式
输入包含两行。
第一行包含两个整数 n 和 k，分别代表数组长度和滑动窗口的长度。
第二行有 n 个整数，代表数组的具体数值。
同行数据之间用空格隔开。
输出格式
输出包含两个。
第一行输出，从左至右，每个位置滑动窗口中的最小值。
第二行输出，从左至右，每个位置滑动窗口中的最大值。
输入样例：

8 3
1 3 -1 -3 5 3 6 7

输出样例：

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

思路：
找滑窗最小值，遍历数组，更新队头满足滑窗要求，每一次循环判断当当前元素小于队尾元素时，删除队尾元素
添加该元素到队尾，此时滑窗的最小值就是队头元素，因为队列从头到尾是单调递增的
找滑窗最大值同理，队列中元素从头到尾始终是递减的，每次取队头元素

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] sss) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] str = br.readLine().split(" ");
        int n = Integer.parseInt(str[0]);
        int k = Integer.parseInt(str[1]);
        int[] a = new int[n];
        str = br.readLine().split(" ");
        //读取输入数组
        for (int i = 0; i < n; i ++) {
            a[i] = Integer.parseInt(str[i]);
        }
        int[] q = new int[n];
        int 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)
                bw.write(a[q[hh]] + " ");
        }
        bw.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) {
                bw.write(a[q[hh]] + " ");
            }
        }
        br.close();
        bw.close();
    }
}