题目链接 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; }