单调栈

int L[maxn], R[maxn];
int a[maxn];

// 找到左边第一个大于它的元素位置l,和右边第一个大于它的元素位置r
// [l,r]
void init(int n) {
    stack<int> st;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[i] > a[st.top()]) st.pop();
        if (st.empty())
            L[i] = 0;
        else
            L[i] = st.top() + 1;
        st.push(i);
    }
    while (!st.empty()) st.pop();
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && a[i] > a[st.top()]) st.pop();
        if (st.empty())
            R[i] = n-1;
        else
            R[i] = st.top() - 1;
        st.push(i);
    }
}

poj2559 最大公共矩形

给定若干小矩形的高度(默认宽度都为 1),求出最大公共矩形。

分析

我们想知道每个矩形向右能扩展多大和向左能扩展多大。
枚举当然可以,这里介绍一种复杂度更低的做法,单调栈。
从左向右遍历。保持栈里元素单调递增。对于每个 pop 出来的矩形,可以得到
它所对应的左右扩展的位置。具体可以看代码

代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<stack>
using namespace std;
typedef long long ll;
ll ans;
int n;
ll num[100005];
void solve(){
    stack<pair<int, ll > > st;
    for(int i= 0 ; i < n; i++){
        int pos = i;  //记录向左可扩展到的位置
        while(st.size() && num[i] < st.top().second){
            pair<int,ll> temp = st.top();
            pos = temp.first;
            st.pop();
            ans = max(ans,(i - temp.first)*temp.second);
        }
        st.push(make_pair(pos,num[i]));
    }
    while(st.size()){  //若栈不为空,则继续pop
        pair<int,ll> temp = st.top();
        st.pop();
        ans = max(ans, (n - temp.first)*temp.second);
    }
}
int main(){
    while(scanf("%d",&n) != EOF){
        if(!n) break;
        for(int i=0;i<n;i++){
            scanf("%lld",&num[i]);
        }
        ans = -1000000;
        solve();
        printf("%lld\n",ans);
    }
}

单调队列

求滑动窗口最大值

双端队列模拟即可

deque<pii> dq;  // (pos, val)

for(int i=1;i<=n;i++){
    while(dq.size() && 队首过期) dq.pop_front();
    while(dq.size() && 加入当前元素后队列不单调) dq.pop_back();
    dq.push_back(当前元素)
    队首进行决策
}
最后修改:2020 年 07 月 30 日 10 : 25 PM