详 解 – 如何用数组实现最高效的"单调队列"          

🧊常见疑惑

🍐单调队列的实现方式有很多，例如：优先队列、队列、数组…，但我们经常会在大佬们的滑动窗口题解中看到这样的一些代码，例如：

int hh = 0, tt = -1;
for(int i = 0; i < n; i++){
    if(hh <= tt && q1[hh] < i - k) hh++;
    while(hh <= tt && a[q1[tt]] >= a[i]) tt--;
    q1[++tt] = i;
    res[i] = a[q1[hh]];
}

🍐没错，这就是用数组模拟的单调队列，相比于其他数据结构，数组加双指针模拟的单调队列在弹出元素时不必按照常规队列那样不达目的不罢休地一直弹出元素，数组模拟的队列只需要操作一次指针即可实现弹出元素的效果。
🍐初次见到这种数据结构时，我们总是带着自己的猜测去阅读这些看似语义化的变量，就像是在坐过山车，不知道下一秒它们会走到哪里去，别急，让我们一起来看看，它们究竟是何方神圣！？

🧊变量操作说明：

    🧁 q[]：用数组模拟的队列。
    🧁 hh：队头指针。
    🧁 tt：队尾指针。
    🧁 q[++tt]：入队（加入队尾）。
    🧁 hh++：弹出队头。
    🧁 tt--：弹出队尾。
    🧁 q[hh]：队头元素。
    🧁 (hh<=tt)?"false":"true")：判断队列是否为空。

🍭看到这里，你心中的疑惑应该被解开了吧。 什么？没有？！哦~嗯调！…

🍨咳 咳~ 别急，我还有招，请跟我一起看一道经典题目（说不定聪明的你曾经解过此题）

❤️‍🔥经典例题实战讲解 c++/Java（代码在文末）

题目描述：

有一个长度为 n 的数列和一个大小为 k 的窗口, 窗口可以在数列上来回移动.
现在我们想知道在窗口从左往右滑的时候，每次窗口内数的最大值和最小值分别是多少. 例如：
…
input：
输入有两行。第一行两个整数n和k分别表示数列的长度和滑动窗口的大小，1 ≤ k ≤ n ≤ 1000000。第二行有n个整数表示数列。
…
output：
输出有两行。第一行输出滑动窗口在从左到右的每个位置时，滑动窗口中的最小值。第二行是最大值。
…
样例输入：
8 3
1 3 -1 -3 5 3 6 7
1
2
样例输出：
-1 -3 -3 -3 3 3
3 3 5 5 6 7

思路详解

🍋 用数组模拟队列的解题思路：

🍬最小值和最大值分开来做，两个for循环完全类似，都做以下四步：

    🍒 ①解决队首已经出窗口的问题;
    🍒 ②解决队尾与当前元素a[i]不满足单调性的问题;
    🍒 ③将当前元素下标加入队尾;
    🍒 ④如果满足条件则输出结果;

🍬需要注意的几个点（边看边思考为什么）：

    🍒 上面四个步骤中一定要先3后4，因为有可能输出的正是新加入的那个元素。
    🍒 队列中存的是原数组的下标，取值时要再套一层，a[q[hh]]。
    🍒 算最大值前注意将hh和tt重置。
    🍒 hh从0开始，数组下标也要从0开始。

🍬补充一下关于hh、tt初始化的细节：

    🍒 hh, tt的初始化是与数组第一个值下标有关的： hh≤数组第一个下标 （如数组从0开始，hh≤0；数组从1开始，hh≤1，可以是1/0/-1等等）
    🍒 对于数组第一个值下标从0还是从1开始,还会影响输出时的if判断,需要对应修改:
        🍒下标从0开始，就是i>=k-1，因为第一个窗口为0 1 2；
        🍒下标从1开始，就是i>=k，因为首个窗口是1 2 3；
    🍒 队头在左边，hh++ 表示出队，tt++ 表示入队。
    🍒 if (i + 1 >= k) printf(“%d “, a[q[hh]]); 这里的i+1>=k是什么意思，为什么这个时候输出？
        🍒构成滑动窗口。
        🍒窗口里一定要有k个数才能开始找最值，像样例里面的k=3，窗口里的数在一开始是从0加到3，在没到3之前都不能输出队头。

🍬回到我们最初的问题：那个for循环是干啥的？它里面究竟是怎么走的？

🍬下面是在完整代码中截取的一段核心代码，注释里面有详细的解释,请各位小伙伴认真阅读！~

        for (int i = 0; i < n; i++) {
            in.nextToken();
            a[i] = (int) in.nval;
            //上面两行是接收输出的值
            
	/*下面这个if语句，你可以理解为一个动作，即：滑动窗口（动词）！！！ 
	比如：k=3的时候，假设我已经走到了下标为4的位置，我们的窗口框定的元素为2,3，4；
	那么，当前窗口最多包含到下标为2的元素，而不可能包含到下标1，
	所以我们要移动队头到窗口所规定的范围内，例如通过hh++ 将指针从1移动到2。 */
            if (i - k + 1 > q[hh]) hh++;//若队首出窗口，hh加1
            while (hh <= tt && a[i] <= a[q[tt]]) tt--;//若队尾不单调，tt减1
            /*你或许会想到队头和队尾重合的情况，但是这种情况是很正常的，
            队列里面只有一个元素的时候，队头和队尾都是它，其他时候队尾是在后面的*/
            q[++tt] = i;//将下标加到队尾。
			//下面这句话并非模板操作，只是根据题意要输出相应内容而加上的。
            if (i + 1 >= k) System.out.print(a[q[hh]] + " ");//输出结果
        }

AC代码

Java

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;
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    public static void main(String[] args) throws IOException {
        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int k = (int) in.nval;

        for (int i = 0; i < n; i++) {
            in.nextToken();
            a[i] = (int) in.nval;
            if (i - k + 1 > q[hh]) hh++;//若队首出窗口，hh加1
            while (hh <= tt && a[i] <= a[q[tt]]) tt--;//若队尾不单调，tt减1
            q[++tt] = i;//将下标加到队尾。
            if (i + 1 >= k) System.out.print(a[q[hh]] + " ");//输出结果
        }
        System.out.println();
        hh = 0;//重置
        tt = -1;//重置
        for (int i = 0; i < n; i++) {
            if (i - k + 1 > q[hh]) hh++;
            while (hh <= tt && a[i] >= a[q[tt]]) tt--;
            q[++tt] = i;
            if (i + 1 >= k) System.out.print(a[q[hh]] + " ");
        }
    }
}

C++

# include <iostream>
using namespace std;
const int N = 1000010;
int a[N], q[N], hh, tt = -1;

int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; ++ i)
    {
        scanf("%d", &a[i]);
        if (i - k + 1 > q[hh]) ++ hh;                  // 若队首出窗口，hh加1
        while (hh <= tt && a[i] <= a[q[tt]]) -- tt;    // 若队尾不单调，tt减1
        q[++ tt] = i;                                  // 下标加到队尾
        if (i + 1 >= k) printf("%d ", a[q[hh]]);       // 输出结果
    }
    cout << endl;
    hh = 0; tt = -1;                                   // 重置！
    for (int i = 0; i < n; ++ i)
    {
        if (i - k + 1 > q[hh]) ++ hh;
        while (hh <= tt && a[i] >= a[q[tt]]) -- tt;
        q[++ tt] = i;
        if (i + 1 >= k) printf("%d ", a[q[hh]]);
    }
    return 0;
}

🐳结语

🐬初学一门技术时，总有些许的疑惑，别怕，它们是我们学习路上的点点繁星，帮助我们不断成长。

🐟文章粗浅，希望对大家有帮助！

🦄参考文章： 滑动窗口（单调队列）、滑动窗口(单调队列)