时间戳

首页 > 技术文章 > 【算法学习笔记】单调队列

【算法学习笔记】单调队列

RioTian 2021-07-27 10:44 原文

单调队列，就是单调的队列，通常用来解决滑动窗口的最值问题，可以应用到 DP 的优化上。一个单调队列中的元素总是单调递增（或递减）的。

例：有一个队列，每次从队尾加入一个元素，或从队首删除一个元素，并在任何时刻求整个队列的最大值。

一个很直接的想法是使用优先队列 priority_queue 即堆，堆可以在 \(\mathcal{O}(1)\) 的时间内求出最大值，但每次加入或删除时需要 \(\mathcal{O}(log\ n)\) 的时间完成堆的调整，但是用了堆后就不能按照进队的顺序出队了！这时候你可以大胆地写一个平衡树或者 set——如果你不怕多出来的 和平衡树常数带来的 TLE 的话。

单调队列就是解决这类问题的数据结构，我们用一个辅助队列，使该队列的首元素总是原队列的最大值，这样就可以 地求出队列的最大值了。

维护单调队列

现有需要维护最大值的队列 Q，和辅助队列 M，设计算法使任何时刻时 M 队首元素都是当前 Q 的最大值。

每次在 Q 的队尾加入元素 x 时，也将其加入到 M 中，从 M 的队尾向前遍历，将遍历到的所有 小于等 x 的元素全部删除，因为它们在 x 之前被加入到队列中，在 x 出队前它们就已经都出队了，即在 x 出队前这些元素不可能成为队列中的最大值。

每次在 Q 的队首删除元素时，将要删除的元素与 M 的队首元素比较，如果该元素与 M 队首元素相等，即该元素为执行删除操作前队列的最大值，则同时也要将 M 的队首元素删除，使原 Q 的次小值成为 M 的队首元素，保证 M 的队首元素是删除操作后 Q 中最大的元素。

应用

状态转移方程形如 \(f[x] = max\{g(k) + w[x]\}\) 的动态规划可以使用单调队列来优化。

实现

因为同时要从队列的两端添加、删除，所以要使用 deque 实现，而不是 queue。

当然也可以手写数组模拟 deque

template<typename T>
struct MonotoneQueue {
    deque<T>q, m;

    void push(const T &x) {
        q.push_back(x);
        while (!m.empty() and m.back() < x) m.pop_back();
        m.push_back(x);
    }
    
    void pop() {
        T x = q.front();
        q.pop_front();
        if (x == m.front()) m.pop_front();
    }
    
    size_t size() {return q.size();}
    T top() {return m.front();}
};

单调队列模板题：P1440 求m区间内的最小值

// 不使用范式以及辅助deque的写法
const int N = 2e6 + 10;
int a[N];
deque<int>q;
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    cout << "0\n";
    for (int i = 1; i < n; ++i) {
        if (i > m and q.front() == a[i - m]) q.pop_front();
        while (!q.empty() and q.back() > a[i]) q.pop_back();
        q.push_back(a[i]);
        cout << q.front() << "\n";
    }
}

同时单调队列常常和二分结合起来解决问题，要注意灵活使用。

单调队列优化DP练习：Here

推荐阅读