单调队列

约 170 个字 12 行代码 预计阅读时间 1 分钟

$O(n)$ 解决滑动窗口类问题，即序列中每个长度m的区间最值

维护一个双向队列deque，表示可能是区间最值的元素

遍历序列，当新旧元素序号之差大于等于m，说明新旧元素不在一个长度m的区间，旧元素出队

当新元素大于旧元素，说明旧元素永远不可能成为区间最值，旧元素出队

根据上面操作过程，显然队列内元素单调递减

组的题里有专门考单调队列的，但是区域赛真题大多是用单调队列优化DP的

deque<int> q;
int a[N];
for (int i = 0; i < n; ++i)
{
    if (!q.empty() && i - q.front() >= m)
        q.pop_front();
    while (!q.empty() && a[q.back()] < a[i])
        q.pop_back();
    q.push_back(i);
    if (i >= m - 1)
        cout << a[q.front()] << " ";
}