如何用数组实现最高效的”单调队列”

🌷 仰望天空，妳我亦是行人.✨
🦄 个人主页——微风撞见云的博客🎐
🐳 数据结构与算法专栏的文章图文并茂🦕生动形象🦖简单易学！欢迎大家来踩踩~🌺
🪁 希望本文能够给读者带来一定的帮助🌸文章粗浅，敬请批评指正！🐥

文章目录

🧊常见疑惑
❤️‍🔥经典例题实战讲解 c++/Java（代码在文末）
- 题目描述：
- 思路详解
- AC代码
- - Java
  - C++
🐳结语

🧊常见疑惑

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

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：队头指针，记录队列q中存放最值元素下标的下标（最大或最小根据题意来定）你可能会觉得有点绕，q[i]是存放数组元素的下标，而hh是记录q[i]的下标，所以是下标的下标，这里需要多理解理解。
    🧁 tt：队尾指针，记录队列q中队尾的下标。
    🧁 q[++tt]：入队，将某元素的下标加入队尾。
    🧁 hh++：弹出队头，移动一位就等同于改变了队头的位置。
    🧁 tt--：弹出队尾，不符合单调情况的元素就要被弹出！
    🧁 q[hh]：队头，存储了最值元素的下标。
    🧁 (hh<=tt)?"false":"true")：判断队列q是否为空。

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

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

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

题目描述：

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

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

（~~完整的code已于2023年3月24日更新，脉络清晰、讲解更加详、更加细通俗易懂~~ ）

        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 = (int) (1e6 + 10);
    static int n, k;
    static int[] small = new int[N];//存放窗口最大值
    static int[] big = new int[N];//存放窗口最小值
    static int[] a = new int[N];
    static int[] q = new int[N];
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        n = nextInt();
        k = nextInt();
        for (int i = 0; i < n; i++) a[i] = nextInt();
        //从左往右找最小
        int hh = 1, tt = 0;
        for (int i = 0; i < n; i++) {
            while (hh <= tt && a[q[tt]] > a[i]) tt--;//如果队列不为空，并且队尾元素大于当前元素（不单调）则队尾依次弹出
            q[++tt] = i;//符合单调性 或者 弹出完毕,则当前元素入队
            if (q[tt] - q[hh] + 1 > k) hh++;//如果当前队列长度大于窗口长度了，就要弹出队首元素
            small[q[tt]] = a[q[hh]];//将移动方向最前端的元素位置作为small数组下标，然后将队首记录的最小值下标传到a数组里面，将a数组的该元素的值记录在small里面
        }
        //从右往左找最大
        //重置队列
        //至于说为什么只需要重置指针，原因是这样的：
        //队列中的元素是根据指针位置依次入队的，我们不会访问到没有被指针扫过的地方，所以不用担心不小心访问到其他元素等问题
        hh = 1;
        tt = 0;
        //往左走（这道题这么写也没错，但其实没必要，往右走的代码在下面。不过有些题是需要同时走的，所以还是都熟悉一下吧）
        for (int i = n - 1; i >= 0; i--) {
            while (hh <= tt && a[q[tt]] < a[i]) tt--;//这里还是判断单调性，只不过现在的队列从队首到队尾是单调递减的，需要改个条件
            q[++tt] = i;//符合单调性 或者 弹出完毕,则当前元素入队
            //和上面一样，这里是判断队列大小是否超越了窗口大小，值得注意的是：这里的是hh - tt,为啥? 记住一句话————”大的减小的“
            //因为我们是从后面的元素开始入队的，那先入队的元素下标肯定比后入队的元素下标大啊，而先入队的在队头，所以是hh - tt了呗
            if (q[hh] - q[tt] + 1 > k) hh++;
            big[q[tt]] = a[q[hh]];
        }
        /*//往右走
        for (int i = 0; i < n; i++) {
            while (hh <= tt && a[q[tt]] < a[i]) tt--;//如果队列不为空，并且队尾元素大于当前元素（不单调）则队尾依次弹出
            q[++tt] = i;//符合单调性 或者 弹出完毕,则当前元素入队
            if (q[tt] - q[hh] + 1 > k) hh++;//如果当前队列长度大于窗口长度了，就要弹出队首元素
            big[q[tt]] = a[q[hh]];//将移动方向最前端的元素位置作为small数组下标，然后将队首记录的最小值下标传到a数组里面，将a数组的该元素的值记录在small里面
        }*/
        for (int i = k - 1; i < n; i++) out.print(small[i] + " ");
        out.println();
        //往左走，需要思考打印的起始位置：往左，意味着最左边是终点，而我们是从右边窗口大小位置记录的
        for (int i = 0; i < n - k + 1; i++) out.print(big[i] + " ");
//      for (int i = k - 1; i < n; i++) out.print(big[i] + " ");//往右走
        out.flush();
    }

    static int nextInt() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }
}

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;
}