文章目录
前言
一、单调队列
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; }
二、时间复杂度
关于单调队列的各操作时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
