单调栈模板

一：Largest Rectangle in a Histogram[一维单调栈]

题目大意：

　　求最大矩形面积

收获：

　　单调栈的应用

stl栈模拟：

#include<cstdio>
#include<stack>
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll a[N],l[N],r[N];
int main()
{
    int n;
    while(~scanf("%d",&n)&&n){
        stack<int>st;
        for(int i=1;i<=n;++i) scanf("%I64d",&a[i]);
        a[0]=a[n+1]=-1;//头尾均为-1,正常标记l[i]
        for(int i=0;i<=n+1;++i){

            while(!st.empty()&&a[st.top()]>a[i]){
                r[st.top()]=i;
                st.pop();
            }
            if(!st.empty()) l[i]=st.top()+1;
            st.push(i);
        }
        ll ans=0;
        for(int i=1;i<=n;++i){
            if(ans<(r[i]-l[i])*a[i])
                ans=(r[i]-l[i])*a[i];
        }
        printf("%I64d
",ans);
    }
    return 0;
}

数组模拟栈：

二：Largest Submatrix of All 1’s[二维单调栈]

题目大意：

　　从0-1地图上找最大的矩形面积

收获：

　　二维的单调栈可直接遍历

#include<cstdio>
#include<stack>
typedef long long ll;
using namespace std;
const int N=2010;
int vis[N][N];
int l[N],r[N];
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){
                scanf("%d",&vis[i][j]);
                if(vis[i][j]&&i!=1)
                    vis[i][j]+=vis[i-1][j];
            }
        }
        int ans=0;
        stack<int>st;
        for(int i=1;i<=n;++i){
            vis[i][0]=-1,vis[i][m+1]=-1;//为了使整个栈内元素均有用,使得正常标记l[j]
            for(int j=0;j<=m+1;++j){

                while(!st.empty()&&vis[i][st.top()]>vis[i][j]){
                    r[st.top()]=j;
                    st.pop();
                }
                if(!st.empty()) l[j]=st.top()+1;
                st.push(j);
            }
            for(int k=1;k<=m;++k)
                ans=max(ans,(r[k]-l[k])*vis[i][k]);

        }
        printf("%d
",ans);
    }
    return 0;
}