双端队列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; } ```