单调队列

贡献者：有机物

预备知识　队列

　　单调队列和单调栈类似，内部的元素都是单调递增或者递减的，单调队列的思想也是及时排除一定不是最优的选择。单调队列的时间复杂度也是 $O(n)$。

　　单调队列通常处理滑动窗口类的问题，例题。题意大致为：有一个大小为 $k$ 的滑动窗口，每次要输出窗口中的最大值和最小值。

　　举例：

　　该数组为 [1 3 -1 -3 5 3 6 7]，$k$ 为 $3$。

表1：示例

窗口位置	最小值	最大值
[1 3 -1] -3 5 3 6 7	-1	3
1 [3 -1 -3] 5 3 6 7	-3	3
1 3 [-1 -3 5] 3 6 7	-3	5
1 3 -1 [-3 5 3] 6 7	-3	5
1 3 -1 -3 [5 3 6] 7	3	6
1 3 -1 -3 5 [3 6 7]	3	7

　　同样，我们来思考一下朴素算法怎么做，我们用一个队列（这里的队列指双端队列，两端都可以弹出元素）来维护窗口，每次往后移动一位就是往队尾插入一个数，队头删除一个数。要移动 $k$ 次窗口，每次求最小值和最大值就线性枚举一下整个队列，时间复杂度 $O(n\times k)$。

　　如何去优化？思想和单调栈类似，如果 $a_i \geqslant a_j$，那显然 $a_i$ 永远不会作为答案输出。因为 $a_j$ 比 $a_i$ 小，因为求的是最小值，所以输出 $a_j$ 肯定比输出 $a_i$ 要好，所以遇到这种情况就直接把 $a_i$ 删了就行了。所以删除完之后，队列中的元素也就单调上升了。那具有单调性有什么用呢？没有单调性之前要求出最小值我们需要 $O(n)$ 的时间复杂度扫描一遍，具有单调性之后，队头肯定是最小的元素，所以直接 $O(1)$ 输出队头元素就好了。所以单调队列的时间复杂度就是 $O(n)$。

　　具体做法：每次加入一个元素之前判断元素队尾元素是不是比要插入的元素大或相等，如果满足的话删除队尾元素，所以求最小值直接输出队头元素。

cin >> n >> k;
for (int i = 0; i < n; i ++ ) cin >> a[i];

int hh = 0, tt = -1;  // hh 队头，tt 队尾
for (int i = 0; i < n; i ++ )
{
    if (hh <= tt && i - q[hh] + 1 > k) hh ++ ;  // 如果队列大小大于窗口的大小，则队头出队
    while (hh <= tt && a[i] <= a[q[tt]]) tt -- ;
    q[ ++ tt] = i;
    if (i + 1 >= k) cout << a[q[hh]] << ' ';    // i + 1 就是满足窗口大小的队列，每次输出队头
}
cout << endl;

hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
    if (hh <= tt && q[hh] < i - k + 1) hh ++ ;
    while (hh <= tt && a[i] >= a[q[tt]]) tt -- ;  // 求最大值过程对称做一下
    q[ ++ tt] = i;
    if (i + 1 >= k) cout << a[q[hh]] << ' ';
}