经典面试题--寻找01矩阵中最大的1矩形(POJ 3494) - - 博客频道 - CSDN.NET

Leetcode 85 - Maximal Rectangle
POJ地址：http://poj.org/problem?id=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.

题目简述

题目的描述很简单，在一个M * N的矩阵中，所有的元素只有0和1， 找出只包含1的最大矩形。
例如：图中是一个４　×　６的矩形，画出红色的是我们要找到的区域。

这样的话，其实我们要找到的某个矩形就转换成 一某一个行开始的 histogram的最大矩形问题了。

那么我们原始矩形可以变成如下的形式的数据：

第一行表示，我们以第一行作为底边，所形成的 histogram的高度，其他行也类似。

所以问题变成了 枚举每一行，然后求出每一行对应的histogram的最大矩形。

关于histogram求最大矩形

可以看看 http://blog.csdn.net/hopeztm/article/details/7868581

1. int nRow, nCol;  
2. int matrix[MAX_LEN][MAX_LEN]; //原数据  
3. int heights[MAX_LEN][MAX_LEN];//用这个数组来描述 histogram，其中heights[i]表示 以第i行走底的histogram，里面的元素表示对应列的高度  
4. struct Node  
5. {  
6.     int height;  
7.     int position;  
8.     Node(int _height, int _from): height(_height), position(_from)  
9.     {  }  
10.     Node()  
11.     {  }  
12. };  
13. int max(int a, int b)  
14. {  
15.     return a>b ? a : b;  
16. }  
17. int GetArea(int iRow) //用单调栈来枚举其中以 某一行做底的 histogram 所得到的最大矩形面积。  
18. {  
19.     topID = 0;  
20.     push(Node(-1, 0)); 
21.     int i;  
22.     int area, maxArea = 0;  
23.     int position, height;
24.     for( i = 0; i <= nCol; i++)  
25.     {  
26.         position = i + 1;  
27.         if(i == nCol)  
28.         {  
29.             height = -1;  
30.         }  
31.         else  
32.         {  
33.             height = heights[iRow][i];  
34.         }  
35.         Node t(height, position);  
36.         while(top().height > height)  
37.         {  
38.             t = top();  
39.             pop();  
40.             area = (position - t.position) * t.height;  
41.             if(area > maxArea)  
42.             {  
43.                 maxArea = area;  
44.             }  
45.         }  
46.         push(Node(height, t.position));  
47.     }  
48.     return maxArea;  
49. }  
50. int main()  
51. {  
52.     while(scanf("%d%d", &nRow, &nCol) != EOF)  
53.     {  
54.         int i,j;  
55.         int b;  
56.         for( i = 0;i < nRow; i++)  
57.         {  
58.             for( j = 0; j < nCol; j++)  
59.             {  
60.                 scanf("%d", &matrix[i][j]);   
61.             }  
62.         }  
63.                 //求histogram，求的时候，如果以 i 行为底边，j对应的高度是 从i 到 最高连续的1 的数量  
64.         memcpy(heights, matrix, sizeof(matrix));  
65.         for( i = 0; i < nCol; i++)  
66.         {  
67.             for( j = 1; j < nRow; j++)  
68.             {  
69.                 if(heights[j][i] != 0)  
70.                 {  
71.                     heights[j][i] += heights[j-1][i];  
72.                 }  
73.             }  
74.         }  
75.         int maxArea = 0, Area;  
76.         for( i = 0; i < nRow; i++)  
77.         {  
78.             Area = GetArea(i);  
79.             maxArea = max(maxArea, Area);  
80.         }  
81.         printf("%d\n", maxArea);  
82.     }   
83. }  

Read full article from 经典面试题--寻找01矩阵中最大的1矩形(POJ 3494) - - 博客频道 - CSDN.NET