单调队列

文章目录

前言

一、单调队列

1.单调队列

2.AcWing 154. 滑动窗口

题目分析：

AC代码

二、时间复杂度

前言

复习acwing算法基础课的内容，本篇为讲解基础算法：单调队列，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。

一、单调队列

1.单调队列

同单调栈一样，在单调队列的元素中，同样也是按照从大到小或是从小到大的顺序进行排列的，有关单调栈，详见博客：单调栈，本博客关于单调队列是用数组模拟队列，如何用数组模拟队列见博客用数组模拟队列，这里不做赘述，关于单调队列的应用和作用，我们由一道题目展开.

2.AcWing 154. 滑动窗口

本题链接：滑动窗口

本博客给出题目截图：

题目分析：

我们用a数组来代表题目中的数组，然后用q数组代表队列，其中q[i]代表的队列中第i - hh+ 1的点在数组a中的下标，比如当hh = 1的时候，i = 3，那么q[3]代表的就是队列里的第三个点在数组a中的下标

通过样例来进行说明，本题要输出一行最小值和一行最大值，这里拿最小值去距举例：

1 3 -1 -3 5 3 6 7

我们可以观察到只要-1存在的话3和1就不会被输出出去，意味着这两个数是没有意义的，也就是说，当-1被输入进来后，我们可以把3和1直接删除，具体到队列中，就意味着，如果输入的元素要小于等于队尾元素的话，我们就可以把队尾元素删除，直到队尾元素要小于输入的元素或者队列为空就停止删除操作，这一步的代码为while (tt >= hh && a[q[tt]] >= a[i]) tt --;，同时如果i - k + 1 > q[hh]，即队列头的坐标如果不在我们滑动窗口中的时候，我们就让hh ++;，最后说一下输出：当i遍历到第k个点的时候开始输出第一个最小值，因为我们的队列是从坐标0开始的，所以只有当i - 1 >= k的时候我们会开始输出最小值，因为队列中是满足单调递增的，而我们的队列维护的就是滑动窗口的区间，所以对头元素就是我们的最小值，注意对头元素的表示为a[q[hh]]

AC代码

#include <cstdio>
using namespace std;
const int N = 1000010;
int q[N], a[N];
int main()
{
    int n, k;
    int hh = 0, tt = -1;
    scanf ("%d%d", &n, &k);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    //计算最小值
    for (int i = 0; i < n; i ++ ) 
    {
        while (tt >= hh && a[q[tt]] >= a[i]) tt --;
        q[ ++ tt] = i;
        if (tt >= hh && q[hh] < i - k + 1) hh ++;
        if (i >= k - 1) printf("%d ", a[q[hh]]);
    }
    puts("");
    //计算最大值
    tt = -1, hh = 0;                    //这里一定要注意重新更新 hh 和 tt
    for (int i = 0; i < n; i ++ )
    {
        while (tt >= hh && a[q[tt]] <= a[i]) tt --;
        q[ ++ tt] = i;
        if (tt >= hh && q[hh] < i - k + 1) hh ++;
        if (i >= k - 1) printf("%d ", a[q[hh]]);
    }
    return 0;
}

二、时间复杂度

关于单调队列的各操作时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。