首页 > 代码库 > 1158 全是1的最大子矩阵
1158 全是1的最大子矩阵
1158 全是1的最大子矩阵
基准时间限制：1 秒 空间限制：131072 KB
给出1个M*N的矩阵M1，里面的元素只有0或1，找出M1的一个子矩阵M2，M2中的元素只有1，并且M2的面积是最大的。输出M2的面积。
Input
第1行:2个数m,n中间用空格分隔(2 <= m,n <= 500)第2 - N + 1行：每行m个数，中间用空格分隔，均为0或1。
Output
输出最大全是1的子矩阵的面积。
Input示例
3 31 1 01 1 10 1 1
Output示例
4
思路：单调栈；
先预处理出每行中连续1的个数，然后看每列，像这样用单调栈维护当前点能扩展到的最大范围，然后面积是（R[i]-L[i]）*ans[i];
然后更新最大值；复杂度O（n*m）；
1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<string.h> 5 #include<stdlib.h> 6 #include<queue> 7 #include<set> 8 #include<vector> 9 #include<map>10 #include<stack>11 using namespace std;12 typedef long long LL;13 typedef struct node14 {15 int x;16 int id;17 } ss;18 stack<ss>sta;19 int a[600][600];20 int b[600][600];21 int L[600];22 int R[600];23 int main(void)24 {25 int n,m;26 while(scanf("%d %d",&n,&m)!=EOF)27 {28 int i,j;29 for(i = 1; i <= n; i++)30 {31 for(j = 1; j <= m; j++)32 {33 scanf("%d",&a[i][j]);34 }35 }36 memset(b,0,sizeof(b));37 for(i = 1; i <= n; i++)38 {39 for(j = 1; j <= m; j++)40 {41 if(a[i][j])42 {43 b[i][j] = b[i][j-1]+1;44 }45 //printf("%d ",b[i][j]);46 }47 }48 int maxx = 0;49 for(j = 1; j <= m; j++)50 {51 while(!sta.empty())52 sta.pop();53 for(i = 1; i <= n; i++)54 {55 while(true)56 {57 ss ak ;58 ak.x = b[i][j];59 ak.id = i;60 if(sta.empty())61 {62 L[i] = 1;63 sta.push(ak);64 break;65 }66 else67 {68 ss ac = sta.top();69 if(ac.x > b[i][j])70 {71 sta.pop();72 R[ac.id] = i-1;73 }74 else75 {76 L[i] = ac.id;77 sta.push(ac);78 break;79 }80 }81 }82 }83 while(!sta.empty())84 {85 ss al = sta.top();86 sta.pop();87 R[al.id] = n;88 }89 for(i = 1; i <= m; i++)90 {91 int xx = R[i]-L[i]+1;92 maxx = max(maxx,xx*b[i][j]);93 }94 }95 printf("%d\n",maxx);96 }97 return 0;98 }
1158 全是1的最大子矩阵
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。