单调队列笔记
双端队列deque维护一个严格单调变化的组，可以称为一个单调队列
单调队列因为可以直接对组的两端进行操作，所以可以有效的降低时间复杂度
用单调队列来解决问题，一般是需要得到的某个范围内的最小值或最大值
这里以一道经典的单调队列的题目为例：
题目描述
有一个长为 \(n\) 的序列 \(a\)，以及一个大小为 \(k\) 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。
例如，对于序列 \([1,3,-1,-3,5,3,6,7]\) 以及 \(k = 3\)，有如下过程：
\[\def\arraystretch{1.2} \begin{array}{|c|c|c|}\hline \textsf{窗口位置} & \textsf{最小值} & \textsf{最大值} \\ \hline \verb![1 3 -1] -3 5 3 6 7 ! & -1 & 3 \\ \hline \verb! 1 [3 -1 -3] 5 3 6 7 ! & -3 & 3 \\ \hline \verb! 1 3 [-1 -3 5] 3 6 7 ! & -3 & 5 \\ \hline \verb! 1 3 -1 [-3 5 3] 6 7 ! & -3 & 5 \\ \hline \verb! 1 3 -1 -3 [5 3 6] 7 ! & 3 & 6 \\ \hline \verb! 1 3 -1 -3 5 [3 6 7]! & 3 & 7 \\ \hline \end{array} \]输入格式
输入一共有两行，第一行有两个正整数 \(n,k\)。
第二行 \(n\) 个整数，表示序列 \(a\)
输出格式
输出共两行，第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值
样例输入
8 3
1 3 -1 -3 5 3 6 7
样例输出
-1 -3 -3 -3 3 3
3 3 5 5 6 7
数据范围
对于 \(50\%\) 的数据，\(1 \le n \le 10^5\)；
对于 \(100\%\) 的数据，\(1\le k \le n \le 10^6\)，\(a_i \in [-2^{31},2^{31})\)。
题目所给的窗口 ，我们可以使用一个单调队列来维护，每次移动时，检查新进窗口的元素，和退出窗口的元素
然后输出单调队列的最小值或最大值
可以将朴素做法（使用两次循环）的 \(O(n*k)\) 的时间复杂度优化到 \(O(n+k)\)，得到极大的改进，减少了重复的比较次数
首先的是单调队列的写法，可以采用数组模拟队列的方法或者STL库内的deque
这里先介绍数组模拟的方式：
- 定义数组队列、队列的头、队列的尾
int que[1000010], hh, tt;
- 然后将头和尾元素进行初始化：
int hh = 0, tt = -1;
hh一开始指向的是a[]的第一个元素的下标 \(0\) ，此时队列中的元素个数为 \(0\)，故tt=-1
注意！！！这里的单调队列存储的是a[]数组的下标
先来输出窗口内的最小值：
- 遍历
a[]数组
for (int i = 0; i < n; i++) {
......
}
- 其中，我们需要进行的是队列的维护
if (hh <= tt && i - k + 1 > q[hh]) hh++;
当hh<=tt即队列不为空时，若队列中头元素存储的下标值不在a[]数组的窗口内，那么就将头元素向后移动一位（在严格单调队列中），（相当于弹出头元素）
while (hh <= tt && a[q[tt]] >= a[i]) tt--;
q[++tt] = i;
当hh<=tt即队列不为空时，若新进窗口的元素小于我们单调队列的尾元素存储的下标对应的值，就将尾元素向前移动（相当于弹出队尾元素），直到插入a[i]的下标后形成一个严格单调队列
将a[i]的下标作为尾元素，存进队列中
if (i >= k - 1) printf("%d ", a[q[hh]]);
判断窗口是否完整，输出窗口中的最小值
同理，可以依葫芦画瓢地写出输出窗口中最大值的代码：
hh = 0, tt = -1;//重新初始化
for (int i = 0; i < n; i++) {
if (hh <= tt && i - k + 1 > q[hh]) hh++;
while (hh <= tt && a[q[tt]] <= a[i]) tt--;
q[++tt] = i;
if (i >= k - 1) printf("%d ", a[q[hh]]);
}
下面是使用deque实现的代码：
deque<int> q;
定义队列 q，同样的思想可以得到如下代码：
for (int i = 0; i < n; i++) {
while (!q.empty() && i - k + 1 > q.front()) q.pop_front();
while (!q.empty() && a[i] <= a[q.back()]) q.pop_back();
q.push_back(i);
if (i - k + 1 >= 0) printf("%d ", a[q.front()]);
}
q.empty()判断队列是否为空，q.front()返回队头元素、q.back()返回队尾元素
q.pop_front()弹出队头元素、q.pop_back()弹出队尾元素
最后使用q.clear()清空队列，同理得到剩余部分的代码
核心AC代码如下：
模拟队列：
int n, k;
int a[1000010], q[1000010];
int main()
{
scanf("%d %d", &n, &k);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
int hh = 0, tt = -1;
for (int i = 0; i < n; i++) {
if (hh <= tt && i - k + 1 > q[hh]) hh++;
while (hh <= tt && a[q[tt]] >= a[i]) tt--;
q[++tt] = i;
if (i >= k - 1) printf("%d ", a[q[hh]]);
}
printf("\n");
hh = 0, tt = -1;
for (int i = 0; i < n; i++) {
if (hh <= tt && i - k + 1 > q[hh]) hh++;
while (hh <= tt && a[q[tt]] <= a[i]) tt--;
q[++tt] = i;
if (i >= k - 1) printf("%d ", a[q[hh]]);
}
return 0;
}
使用STL库：
int n, k;
int a[1000010];
deque<int> q;
int main()
{
scanf("%d %d", &n, &k);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
for (int i = 0; i < n; i++) {
while (!q.empty() && i - k + 1 > q.front()) q.pop_front();
while (!q.empty() && a[i] <= a[q.back()]) q.pop_back();
q.push_back(i);
if (i - k + 1 >= 0) printf("%d ", a[q.front()]);
}
printf("\n");
q.clear();
for (int i = 0; i < n; i++) {
while (!q.empty() && i - k + 1 > q.front()) q.pop_front();
while (!q.empty() && a[i] >= a[q.back()]) q.pop_back();
q.push_back(i);
if (i - k + 1 >= 0) printf("%d ", a[q.front()]);
}
return 0;
}