单调栈和单调队列

Oistream / 2024-08-22 / 原文

单调栈和单调队列

单调栈

一般用来解决距离一个数最近且大于或小于的数在哪里

luogu:【模板】单调栈

即维护一个数右边最近的大于它的数在哪里用单调栈实现

//by zengmaoyuan
#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 3e6 + 5;
int n, m;
int a[N], ans[N];
stack<int> st;
int main() {
    FASTIO;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    a[0] = -1;
    st.push(0);
    for (int i = n; i >= 1; i--) {
        while (!st.empty() && a[st.top()] <= a[i]) st.pop();
        if (st.empty()) ans[i] = 0;
        else ans[i] = st.top();
        st.push(i);
    }
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << " ";
    }
    return 0;
}

poj2559 Largest Rectangle in a Histogram & luogu P2659 美丽的序列

经典单调栈模板

考虑对每一个数算贡献，即将每一个数来作为最小值来考虑

令当前数为 $x$

那么这一个区间就不能有比 $x$ 更小的数

贪心得到 $l$ 一定在最近的左边 $ \le x$ 的数的位置再 $+1$

则 $r$ 同理

明显可以用单调栈维护

//by zengmaoyuan
#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 2e6 + 5;
int n, m;
stack<int> st;
int l[N], r[N];
int a[N];
int main() {
    FASTIO;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        l[i] = 0, r[i] = n + 1;
    }
    for (int i = 1; i <= n; i++) {
        while (!st.empty() && a[st.top()] >= a[i]) {
            r[st.top()] = i;
            st.pop();
        }
        l[i] = (st.empty() ? 0 : st.top());
        st.push(i);
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, ll(r[i] - l[i] - 1) * a[i]);
    }
    cout << ans;
    return 0;
}

Mike and Feet CodeForces - 547B

首先，如果只询问一个 $x$ ，那么可以直接用滑窗秒了，但这道题不行
首先观察到输出一定是单调递减的，想想也确实是这样的：毕竟包含的数越多越容易包含进来更小的值
但这样又启发我们：对于一个 $x$ , 它可以继承 $x + 1$ 的答案
所以我们可以先向上一道题一样处理出每个数为最小值时的最大区间
然后记录 $ans$ 数组，对每个数的答案取 $max$ ，最后做一个前缀最大值即可

#include<iostream>
#include<cstdio>
#include<cmath>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=2e5+5;
int a[N];
int st[N];
int l[N],r[N];
int t;
int ans[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    t=0;
    for(int i=1;i<=n;i++)
    {
        while(t>0&&a[st[t]]>=a[i]) t--;
        if(t>0) l[i]=st[t]+1;
        else l[i]=1;
        st[++t]=i;
    }
    t=0;
    for(int i=n;i>=1;i--)
    {
        while(t>0&&a[st[t]]>=a[i]) t--;
        if(t>0) r[i]=st[t]-1;
        else r[i]=n;
        st[++t]=i;
    }
    for(int i=1;i<=n;i++) ans[i]=1;
    for(int i=1;i<=n;i++)
    {
        ans[r[i]-l[i]+1]=max(ans[r[i]-l[i]+1],a[i]);
    }
    for(int i=n;i>=1;i--) ans[i]=max(ans[i],ans[i+1]);
    //cout<<ans<<"\n";
    for(int i=1;i<=n;i++)
    {
        cout<<ans[i]<<" ";
    }
}

单调队列

一般解决一段区间内的最值问题

滑动窗口

模板题，直接维护即可

//by zengmaoyuan
#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 1e6 + 5;
int n, m;
deque<int> qmin, qmax;
int ansmx[N], ansmn[N];
int a[N];
int main() {
    FASTIO;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        while (!qmin.empty() && a[qmin.back()] >= a[i]) qmin.pop_back();
        while (!qmax.empty() && a[qmax.back()] <= a[i]) qmax.pop_back();
        while (!qmin.empty() && i - qmin.front() >= m) qmin.pop_front();
        while (!qmax.empty() && i - qmax.front() >= m) qmax.pop_front();
        qmin.push_back(i);
        qmax.push_back(i);
        ansmx[i] = a[qmax.front()];
        ansmn[i] = a[qmin.front()];
    }
    for (int i = 1; i + m - 1 <= n; i++) {
        cout << ansmn[i + m - 1] << ' ';
    }
    cout << '\n';
    for (int i = 1; i + m - 1<= n; i++) {
        cout << ansmx[i + m - 1] << ' ';
    }
    return 0;
}