Largest Submatrix of All 1’s(单调栈)

题目链接:https://cn.vjudge.net/problem/POJ-3494

Given a m-by-n (0,1)-matrix, of all its submatrices of all 1’s which is the largest? By largest we mean that the submatrix has the most elements.

Input

The input contains multiple test cases. Each test case begins with m and n (1 ≤ m, n ≤ 2000) on line. Then come the elements of a (0,1)-matrix in row-major order on m lines each with n numbers. The input ends once EOF is met.

Output

For each test case, output one line containing the number of elements of the largest submatrix of all 1’s. If the given matrix is of all 0’s, output 0.

Sample Input

2 2
0 0
0 0
4 4
0 0 0 0
0 1 1 0
0 1 1 0
0 0 0 0

Sample Output

0
4

求一个0-1矩阵中全为1的最大子矩阵。
关键是看出最大子矩阵,一定是从某个位置开始,向上连续1到达最高点,然后分别左右延伸得到最大面积,即为最大子矩阵种元素的个数。
因此,先预处理出所有点向上连续1的个数。然后利用单调栈,以这个数为高,每行都是O(n)的左右分别延伸求面积的最大值。这一步就转化为了挑战上的例题:求柱形图中矩形的最大面积。这题难点在于,是二维矩阵,也就是对每一行都用挑战例题中的方法求解。时间复杂度为O(m*n)。

//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<stack>
using namespace std;
const int N=2005;
int a[N][N];
int h[N][N];
int l[N][N],r[N][N];//左边界,右边界
int m,n;
struct node{
	int h,w;
	node(){}
	node(int hh,int ww){
		h=hh;
		w=ww;
	}
};
void hpre(){
	memset(h,0,sizeof(h));
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			if(a[i][j]==0) h[i][j]=0;
			else h[i][j]=h[i-1][j]+1;
		}
	}
}
int solve(){
	stack<node> s;
	hpre();
	for(int i=1;i<=m;i++){
		while(!s.empty()) s.pop();
		for(int j=1;j<=n;j++){
			while(!s.empty()&&s.top().h>=h[i][j]){
				s.pop();
			}
			if(s.empty()) l[i][j]=1;
			else l[i][j]=s.top().w+1;
			s.push(node(h[i][j],j));
		}
	}
	for(int i=1;i<=m;i++){
		while(!s.empty()) s.pop();
		for(int j=n;j>=1;j--){
			while(!s.empty()&&s.top().h>=h[i][j]){
				s.pop();
			}
			if(s.empty()) r[i][j]=m;
			else r[i][j]=s.top().w-1;
			s.push(node(h[i][j],j));
		}
	}
	int ans=0;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			ans=max(ans,h[i][j]*(r[i][j]-l[i][j]+1));
		}
	}
	printf("%d\n",ans);
}
int main(){
	while(~scanf("%d%d",&m,&n)){
		for(int i=1;i<=m;i++){
			for(int j=1;j<=n;j++){
				scanf("%d",&a[i][j]);
			} 
		}
		solve();
	}
	return 0;
}

 

也可以先求从某个位置开始向左有多少连续的1,然后分别向上下延伸

#include <iostream>
#include <stack>
#include<cstdio>
#include<cstring>
using namespace std;
int top,tmp,ans,m,n,i,j,a[2010][2010],t[2010];//t数组代表以a[i][j]为边向上能扩展到哪,之前只向下扩展了 
int main()
{
    stack<int> s;
    while(scanf("%d%d",&m,&n)!=EOF){
        ans=0;
        for(i=1;i<=m;i++){
            a[i][0]=0;
            for(j=1;j<=n;j++){
                scanf("%d",&a[i][j]);
                if(a[i][j]&&a[i][j-1])
                    a[i][j]+=a[i][j-1];
            }
        }
        for(j=0;j<=n;j++)
            a[m+1][j]=-1;
        for(j=1;j<=n;j++){
            for(i=1;i<=m+1;i++){
                if(s.empty()||a[s.top()][j]<=a[i][j]){
                	s.push(i);//把行入栈 
                	t[i]=i;
				}     
                else{
                    while(!s.empty()&&a[s.top()][j]>a[i][j]){
                        top=s.top();
                        t[i]=t[top];
                        s.pop();
                        tmp=(i-t[top])*a[top][j];//下限到上限的距离* 边长 
                        if(tmp>ans)
                            ans=tmp;
                        
                    }
                    s.push(i);
                    //a[top][j]=a[i][j]; 没用 
                }
            }
            while(!s.empty())
                s.pop();
        }
        printf("%d\n",ans);
    }
    return 0;
}

 

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-03 17:37
点赞 评论 收藏
分享
05-11 11:48
河南大学 Java
程序员牛肉:我是26届的双非。目前有两段实习经历,大三上去的美团,现在来字节了,做的是国际电商的营销业务。希望我的经历对你有用。 1.好好做你的CSDN,最好是直接转微信公众号。因为这本质上是一个很好的展示自己技术热情的证据。我当时也是烂大街项目(网盘+鱼皮的一个项目)+零实习去面试美团,但是当时我的CSDN阅读量超百万,微信公众号阅读量40万。面试的时候面试官就告诉我说觉得我对技术挺有激情的。可以看看我主页的美团面试面经。 因此花点时间好好做这个知识分享,最好是单拉出来搞一个板块。各大公司都极其看中知识落地的能力。 可以看看我的简历对于博客的描述。这个帖子里面有:https://www.nowcoder.com/discuss/745348200596324352?sourceSSR=users 2.实习经历有一些东西删除了,目前看来你的产出其实很少。有些内容其实很扯淡,最好不要保留。有一些点你可能觉得很牛逼,但是面试官眼里是减分的。 你还能负责数据库表的设计?这个公司得垃圾成啥样子,才能让一个实习生介入数据库表的设计,不要写这种东西。 一个公司的财务审批系统应该是很稳定的吧?为什么你去了才有RBAC权限设计?那这个公司之前是怎么处理权限分离的?这些东西看着都有点扯淡了。 还有就是使用Redis实现轻量级的消息队列?那为什么这一块不使用专业的MQ呢?为什么要使用redis,这些一定要清楚, 就目前看来,其实你的这个实习技术还不错。不要太焦虑。就是有一些内容有点虚了。可以考虑从PR中再投一点产出
投递美团等公司9个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务