单调队列

一个可以操作头和尾，且内部元素单调的数据结构。可以用STL中的deque实现。

例题: 求长度为n的数组中，每连续m个元素的最小值。

C++代码:

deque<int> dq;
for(int i = 0; i < m; i++) {
    // 若第i个数比队列尾的数小，弹出队列尾的数。
    while (dq.size() && a[i] < a[dq.back()]) {
        dq.pop_back();
    }
    dq.push_back(i);
}
cout << a[dq.front()] << " ";
for(int i = m; i < n; i++) {
    // 弹出已经在长度为m的子区间外的数
    while (dq.size() && i - dq.front() >= m) {
        dq.pop_front();
    }
    // 若第i个数比队列尾的数小，弹出队列尾的数。
    while (dq.size() && a[i] < a[dq.back()]) {
        dq.pop_back();
    }
    dq.push_back(i);
    // 队首元素即为子区间中最小的元素
    cout << a[dq.front()] << " ";
}