单调队列与单调栈

zifuneko · 2025-10-12 21:52:25 · 算法·理论

单调队列

https://oiwiki.com/ds/monotonous-queue/

deque

https://oiwiki.com/lang/csl/sequence-container/#deque

std::deque 是 STL 提供的双端队列数据结构。能够提供线性复杂度的插入和删除，以及常数复杂度的随机访问。

元素访问

与 vector 一致，但无法访问底层内存。其高效的元素访问速度可参考实现细节部分。

at(): v.at(pos) 返回容器中下标为 pos 的引用。如果数组越界抛出 std::out_of_range 类型的异常。执行越界检查，常数复杂度。
operator[]: v[pos]返回容器中下标为 pos 的引用。不执行越界检查，常数复杂度。
front() 返回首元素的引用。
back() 返回末尾元素的引用。

元素增删及修改

与 vector 一致，并额外有向队列头部增加元素的函数。

clear() 清除所有元素
insert() 支持在某个迭代器位置插入元素、可以插入多个。复杂度与 pos 与两端距离较小者成线性。
erase() 删除某个迭代器或者区间的元素，返回最后被删除的迭代器。复杂度与 insert 一致。
push_front() 在头部插入一个元素，常数复杂度。
pop_front() 删除头部元素，常数复杂度。
push_back() 在末尾插入一个元素，常数复杂度。
pop_back() 删除末尾元素，常数复杂度。
swap() 与另一个容器进行交换，此操作是 常数复杂度 而非线性的。

单调队列模版

P1886 滑动窗口 /【模板】单调队列

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAX = 1e6+5;
int a[MAX];

signed main()
{
    int n, k; cin >> n >> k;
    for(int i=1; i<=n; i++) cin >> a[i];

    deque<int> dq;
    for(int i=1; i<=n; i++) // 维护单调递减
    {
        while(!dq.empty() && dq.front() + k <= i) dq.pop_front(); // 淘汰太老的
        while(!dq.empty() && a[dq.back()] >= a[i]) dq.pop_back(); // 淘汰更老且大的
        dq.push_back(i);
        if(i >= k) cout << a[dq.front()] << " "; // 队首一定最小
    }
    cout << endl;
    dq.clear();
    for(int i=1; i<=n; i++) // 维护单调递增
    {
        while(!dq.empty() && dq.front() + k <= i) dq.pop_front(); // 淘汰太老的
        while(!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back(); // 淘汰更老且小的
        dq.push_back(i);
        if(i >= k) cout << a[dq.front()] << " "; // 队首一定最大
    }

    return 0;
}

注意：(!dq.empty() && dq.front() + k <= i) 且与或的短路原理。必须满足 !dq.empty() 否则 dq.front() + k <= i 不会执行。(dq.front() + k <= i && !dq.empty()) 是错误的写法，可能会导致RE.

单调队列与DP结合

更多的，单调队列还有可能和DP结合，如DP需要求一段区间的最值，并且是滑动。

P2034 选择数字

f[i] = \min\limits_{\mathclap{j\in[i-k-1, i-1]}} \normalsize(\{f[j]\}) + \text{val}

#include <bits/stdc++.h>
using namespace std; 
#define int long long
const int N = 1e5+5; 
int a[N], dp[N]; 

signed main()
{ 
    cin.tie(nullptr)->sync_with_stdio(false); 
    memset(dp, 0x3f, sizeof(dp)); 
    dp[0] = 0; 
    int n, k; cin >> n >> k; 
    for(int i=1; i<=n; i++) cin >> a[i]; 

    deque<int> dq = {0}; // 首先把 dp[0] 放进去 
    for(int i=1;i<=n;i++) 
    { 
        // 先弹出所有不能转移过来的位置 
        while(!dq.empty() && dq.front() < i-k-1) dq.pop_front(); 
        // 此时，还没有将 dp[i] 加入队列，队列中最靠右元素为 dp[i-1]; 
        dp[i] = dp[dq.front()] + a[i]; 
        // 维护单调队列 
        while(!dq.empty() && dp[dq.back()] >= dp[i]) dq.pop_back(); 
        dq.push_back(i); 
    } 
    // 最终所求即为所有数字的和减去删除数字的最小和 
    cout << accumulate(a+1, a+n+1, 0LL) - *min_element(dp+n-k, dp+n+1) << endl;

    return 0; 
}

P3957 [NOIP 2017 普及组] 跳房子

f[i] = \max\limits_{\mathclap{j\in[l,r]}} \normalsize(\{f[j]\}) + s[i]

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAX = 5e5+5;

int n, d, k, x[MAX], s[MAX];
long long dp[MAX]; // dp[i] 代表跳到第 i 格时，可以获得的最大分数

bool check(int g) // 在修理 g 元的情况下，能否获得 k 分
{
    memset(dp, 0xcf, sizeof(dp)); // 极小值
    dp[0] = 0;
    deque<int> dq;
    int p = 0;

    for(int i=1; i<=n; i++)
    {
        // 找到所有距离在 [x[i]-d-g, min(x[i]-1, x[i]-d+g)] 的 dp 最大值
        while(x[p] <= min(x[i]-1, x[i]-d+g)) // 把小于等于右端点的入队
        {
            // 维护单调队列
            while(!dq.empty() && dp[dq.back()] <= dp[p]) dq.pop_back();
            dq.push_back(p++);
        }
        // 把所有小于左端点的弹出
        while(!dq.empty() && x[dq.front()] < x[i]-d-g) dq.pop_front();
        if(!dq.empty()) dp[i] = dp[dq.front()] + s[i];
    }
    return *max_element(dp, dp+n+1) >= k;
}

signed main()
{
    cin >> n >> d >> k;
    int sum = 0;
    for(int i=1; i<=n; i++)
    {
        cin >> x[i] >> s[i];
        if(s[i] > 0) sum += s[i];
    }

    if(sum < k) cout << -1 << endl;
    else
    {
        int l=0, r=1e9;
        while(l < r)
        {
            int m = (l+r)/2;
            if(check(m)) r = m;
            else l = m + 1;
        }
        cout << l << endl;
    }

    return 0;
}

单调栈

https://oiwiki.com/ds/monotonous-stack/

P5788 【模板】单调栈

#include<bits/stdc++.h>
using namespace std;

const int MAX = 3e6+5;
int v[MAX], ans[MAX];
stack<int> sk;
int main()
{
    int n; cin >> n;
    for(int i=1; i<=n; i++) cin >> v[i];
    for(int i=n; i>=1; i--)
    {
        while(!sk.empty() && v[sk.top()] <= v[i]) sk.pop();
        if(!sk.empty()) ans[i] = sk.top();
        sk.push(i);
    }
    for(int i=1; i<=n; i++) cout << ans[i] << ' ';
    return 0;
}

大概没什么用。