求最大子矩阵的大小

【说明】：

本文是左程云老师所著的《程序员面试代码指南》第一章中“求最大子矩阵的大小”这一题目的C++复现。

本文只包含问题描述、C++代码的实现以及简单的思路，不包含解析说明，具体的问题解析请参考原书。

感谢左程云老师的支持。

【题目】：

给定一个整型矩阵 map，其中的值只有 0 和 1 两种，求其中全是1的所有矩形区域中，最大的矩形区域为1的数量。

例如：

1 1 1 0

其中，最大的矩形区域有 3 个 1，所以返回3。

再如：

1 0 1 1

1 1 1 1

1 1 1 0

其中，最大的矩形区域有 6 个 1，所以返回6。

【思路】：

简单已经不足以描述了，请参考左老师的原书。

【编译环境】：

CentOS6.7（x86_64）

gcc 4.4.7

【实现】：

实现及测试代码：

1 /*
 2  *文件名：maxRecSize.cpp
 3  *作者：
 4  *摘要：使用C++实现最大子矩阵的问题
 5  */
 6  
 7 #include <iostream>
 8 #include <stack>
 9 #include <algorithm>
10 
11 using namespace std;
12 
13 int maxRecFromBottom(int count[],int len)
14 {
15     if(NULL == count || len <=0 )
16         return 0;
17     int maxArea = 0;
18     stack<int> s;
19     for(int i=0; i<len; i++)
20     {
21         while(!s.empty() && count[i] <= count[s.top()])
22         {
23             //当前的数据位置为i
24             int j = s.top();    //弹出的栈顶数据标记为j
25             s.pop();
26             int k = s.empty() ? -1 : s.top();    //新的栈顶标记为k
27             int curArea = (i-k-1) * count[j];
28             maxArea = max(curArea,maxArea);
29         }
30         s.push(i);
31     }
32     while(!s.empty())
33     {
34         int j = s.top();
35         s.pop();
36         int k = s.empty() ? -1 : s.top();
37         int i = len;    //在len处虽然没有数据，但是len可做为右边界
38         int curArea = (i-k-1)*count[j];
39         maxArea = max(curArea,maxArea);
40     }
41     return maxArea;
42 }
43 
44 int maxRecSize(int **mat,const int length,const int height)
45 {
46     if(NULL == mat || 0 >= length || 0 >= height )
47         return 0;
48     int maxArea = 0;
49     int *count = new int[length]();
50     for(int i=0; i<height; i++)
51     {
52         for(int j=0; j<length; j++)
53         {
54             count[j] = ((mat+i)[j] == 0 ? 0 : count[j]+1);
55         }
56         cout << "--------" << endl;
57         maxArea = max(maxRecFromBottom(count,length),maxArea);
58     }
59     return maxArea;
60 }
61 
62 int main()
63 {
64     int mat[][4] = {{1,0,1,1},{1,1,1,1},{1,1,1,0}};
65     cout << "maxRecSize is : " << maxRecSize((int **)mat,4,3) << endl;
66     return 0;
67 }

View Code
【说明】

1、一维数组初始化时碰到一个问题：

我声明的原代码为：

int count[length] = {0}; //错误：可变大小的对象‘count’不能被初始化

后改为：

int *count = new intlength; //这种情况就可以实现内将为count分配的内存初始化为0

关于C++中使用 new 时，数组初始化的问题请参考：[C++]数组初始化

重点：（错误：ISO C++ 不允许在数组 new 中初始化）new数组只能用无参的构造函数或者所有参数都有默认值的构造函数，new[]（new的数组版）要求元素对象的类型必须具有默认构造函数（内建类型的“默认构造函数”是什么也不做），否则将不能使用new[]。

2、二维指针做形参的问题请参考：[总结]C语言二维数组作为函数的参数

3、使用二维指针访问二维数组时需要注意的请参考：二维数组和二级指针

注：

转载请注明出处；

转载请注明源思路来自于左程云老师的《程序员代码面试指南》
原文链接: https://www.cnblogs.com/PrimeLife/p/5346882.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍