题目1497：面积最大的全1子矩阵
时间限制：1 秒
内存限制：128 兆
特殊判题：否
提交：1019
解决：215
题目描述：
在一个M * N的矩阵中，所有的元素只有0和1，从这个矩阵中找出一个面积最大的全1子矩阵，所谓最大是指元素1的个数最多。
输入：
输入可能包含多个测试样例。对于每个测试案例，输入的第一行是两个整数m、n(1<=m、n<=1000)：代表将要输入的矩阵的大小。矩阵共有m行，每行有n个整数，分别是0或1，相邻两数之间严格用一个空格隔开。
输出：
对应每个测试案例，输出矩阵中面积最大的全1子矩阵的元素个数。
样例输入：2 20 00 04 40 0 0 00 1 1 00 1 1 00 0 0 0样例输出04来源：腾讯2012年暑期实习生招聘面试二面试题
题目链接：?pid=1497
思路：单调栈的应用；O(n*m)；
首先把原矩阵num[][],进行预处理：使得len[i][j],
表示第i行j列为底的最大连续宽度，（len[][]从0行0列开始） if(num[i][j]) len[i][j]=len[i][j-1]+num[i][j]; else len[i][j]=0;
举个例子：设矩阵num（1行，1列开始）为：
0 -1 -1 -1 -1
0 1 1 10 0 1 2 3
1 1 1 0 则相应的len[][]矩阵预处理为： 0 1 2 3 0
1 0 1 10 1 0 1 2
1 1 1 1 01 2 3 4
从最后一列开始遍历，每次从第一行入栈，当后面的数比前面大的时候就入栈，当不大于栈顶的数时，栈顶元素就出栈并计算面积；
处理技巧先入栈0（值一个负数值）保证不会发生段位错误；
举个简单的例子：假设某一列的值为 -1 2 3 5 3 4 2 4
对应的行标为 0 1 2 3 4 5 6 7
首先0压入栈，然后压入1（因为2>-1），然后压入2（因为3>2），然后弹出3（因为3<=5）并计算高为5宽度为W=4-2-1；记录面积tmp=max（tmp，，5*W）；然后弹出2（因为3<=3）并计算高为3宽度为W=4-1-1；记录面积tmp=max（tmp，3*W）；然后压入4；然后压入5；然后弹出5（…..）并计算面积，然后弹出3，并计算面积；然后弹出1并计算面积；然后压入6，最后压入7；最后没有数据了，对栈内元素进行处理面积，依次弹出，宽度为最后一个压入的元素；。。。依次对每列操作，
//小优化，ans表示结果，当ans>=j列*m行时就可以break了。就是这样，注意细节；
这题我以前也写过，现在来更新下，之前的代码可以参考：
思维比较重要！
#include<stdio.h>#include<stack>#include<algorithm>using namespace std;int num[1005][1005];int len[1005][1005];int main(){int m,n;while(scanf("%d %d",&m,&n)!=EOF){for(int i=1;i<=m;i++){len[i][0]=0;for(int j=1;j<=n;j++){len[0][j]=-1;scanf("%d",&num[i][j]);if(num[i][j]) len[i][j]=len[i][j-1]+num[i][j];else len[i][j]=0;}}stack<int> S;int ans=0,tmp;for(int j=n;j>0;j–){ //S.clear();int W,L;tmp=0;if(ans>=j*m) break;S.push(0);for(int i=1;i<=m;i++){if(len[i][j]>len[S.top()][j]) {S.push(i);}else{while(!S.empty()&&len[i][j]<=len[S.top()][j]){L=S.top();S.pop();int p=S.top();W=(i-p-1);tmp=max(tmp,W*len[L][j]);}S.push(i);}}int LL;if(!S.empty())LL=S.top();while(!S.empty()){L=S.top();S.pop();int p=S.top();if(p) W=(LL-p);else {W=LL;S.pop();}tmp=max(tmp,W*len[L][j]);}ans=max(tmp,ans);}printf("%d\n",ans);}return 0;}/*4 40 1 1 01 1 1 00 0 1 11 1 1 1*/
版权声明：本文为博主原创文章，未经博主允许不得转载。
肯承认错误则错已改了一半
