23.单调队列

单调队列

单调队列是一种特殊的队列结构，通过维护队列元素的单调性（递增或递减），可以在O(1)时间内得到一段区间内的最值。

为了维护单调性，通常需要两端都能出队，所以严格意义上说，它并不是一个数据结构定义中的“队列”。 STL 中有一个很方便的容器 deque 来实现双端队列。

单调队列经常与双指针（尺取）一起使用。

例：扫描

\(n\) 个数，长度为 \(k\) 的区间从左往右扫过去，输出每一步长度为 \(k\) 的区间内的最大值

分析：

右边入队、左边出队，可以在队列里维护 \(k\) 区间的数据，但这样还解决不了最大值问题。

要让这个队的右边也出队：在右边新元素入队前，右边比新元素小的都出队。因为随着 \(k\) 区间移动，先入队的肯定先出队，那么先入队却又比右边即将入队元素小的那些已经无“出头之日”了，没必要放在队列里。

这样成功维护了一个左大右小的单调队列。

#include<cstdio>
#include<cstring>
#include<deque>
#include<algorithm>
const int maxn = 2e6 + 10;
int n, k, a[maxn];
int main() {
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i ++) {
        scanf("%d", &a[i]);
    }
    std::deque<int> q;
    for(int i = 0; i < n; i ++) {
        // 左边 超出以 i 为右端的 k 区间的元素出队
        while(!q.empty() && i - q.back() + 1 > k) {
            q.pop_back();
        }
        // 右边比 a[i] 小的出队
        while(!q.empty() && a[q.front()] < a[i]) {
            q.pop_front();
        }
        q.push_front(i);
        // 队内最左边的是当前 $k$ 区间最大值
        if(i >= k - 1) {
            printf("%d\n", a[q.back()]);
        }
    }
    return 0;
}