题目链接 1158 全是1的最大子矩阵

题意

给出1个M*N的矩阵M1，里面的元素只有0或1，找出M1的一个子矩阵M2，M2中的元素只有1，并且M2的面积是最大的。输出M2的面积。

思路

使用单调栈，来储存最大的连续的1，求出每行每个位置的能连续1的最大值。例子中的矩阵变为：

1 2 0

1 2 3

0 1 2

然后发现对于每一列来说，要求的是一个区间内的最小值乘以区间长度，所有这些值的最大值。这就是对一个元素的两边进行扩展，发现这就是单调栈的应用了。

代码

#include<stdio.h>  
#include<string.h>  
#include<iostream>  
#include<stack>  
using namespace std;  

int main()  
{  
    //top指向栈顶；tmp为临时变量，记录面积的值；ans为答案，记录面积的最大值   
    int i,j,m,n,x,top,tmp,ans,h[2020],a[2020];  
    stack<int> st; //单调栈，记录位置   
    while(~scanf("%d%d",&m,&n))  
    {  
        ans=0;  
        memset(h,0,sizeof(h)); //用于第一行的处理  
        for(i=0;i<m;i++)  
        { //扫描每一行   
            for(j=1;j<=n;j++)  
            {  
                scanf("%d",&x);  
                if(x==1) h[j]=h[j]+1; //如果是1，则在上一行本列的基础上+1   
                else h[j]=0; //否则为0   
                a[j]=h[j]; //a数组用来向左右扩展  
            }  
            a[n+1]=-1; //设最后元素为最小值，以最后让栈内元素出栈   
            for(j=1;j<=n+1;j++)  
            {  
                if(st.empty()||a[j]>=a[st.top()])  
                { //如果栈为空或入栈元素大于等于栈顶元素，则入栈   
                    st.push(j);  
                }  
                else  
                {  
                    while(!st.empty()&&a[j]<a[st.top()])  
                    { //如果栈非空并且入栈元素小于栈顶元素，则将栈顶元素出栈   
                        top=st.top();  
                        st.pop();  
                        tmp=(j-top)*a[top]; //计算面积值   
                        if(tmp>ans) ans=tmp; //更新面积最大值   
                    }  
                    st.push(top); //将最后一次出栈的栈顶元素延伸并入栈   
                    a[top]=a[j]; //修改其对应的值   
                }  
            }  
        }  
        printf("%d\n",ans);  
    }  
    return 0;  
}