求直方图中最大矩形的面积，用这个思路可以进一步解决求01矩阵中最大的全0或全1矩阵
直方图中最大矩形的面积
问题描述
给定一个一维数组，代表直方图中每个区间的高度，求出直方图中最大矩形的面积，图中区间的宽度为1。
图中所示一维数组为[2,1,5,6,2,3]，那么所求的矩形应该是5和6区间构成的矩形，面积为5*2=10。
求解算法
这个问题的核心思想是依次计算每个区间能够构成的最宽矩形面积，再从中选出面积最大的。
首先考虑一下有序序列，这样的直方图可以用统一的算法来求解每个区间的矩形面积：从后往前遍历，假设最后一个数值为，它的索引为
，当前遍历到的数值索引为
，那么当前区间构成的矩形面积就为
，再设置一个max变量，记录遍历过程中出现的最大值就行了。
但是问题在于这些数字都是无序的，不好用这种统一的方法来计算矩形面积，所以引入了栈结构，目的就是从序列中挑出有序的部分来计算，确切地说是保持栈内的元素都是升序排列，而且每个元素都入栈一次。
具体做法是：
1、将序列中的元素索引依次入栈，若当前索引对应的数值大于栈顶元素对应的数值时时，将索引顺利入栈；要是小于栈顶元素对应的数值，说明这是逆序，执行第2步；
2、把栈顶元素输出，得到这个索引对应的数值，计算这个数值代表区间的最大矩形面积（此时按照有序时的公式，就是刚才要入栈但是发现逆序没入成的那个索引值-1，
则是现在pop出来的索引值），计算完更新max变量，再返回第1步；
3、当所有元素都入栈之后，若栈内还有元素，就依次pop出来计算面积，实质上就是处理剩下的有序序列了。
代码实现
int getMaxArea(vector<int> array){
int len=array.size();
if (len==0) return 0;
stack<int> s;
int max=array[0];
s.push(0);
for (int i=1;i<len;){
int cur=array[s.top()];
if (array[i]>=cur){
s.push(i);
i++;
}else{
int top=array[s.top()];
int curMax=top*(i-s.top());
s.pop();
if (curMax>max) max=curMax;
}
}
if (!s.empty()){
int last=s.top();
while (!s.empty()){
int top=array[s.top()];
int curMax=top*(last-s.top()+1);
s.pop();
if (curMax>max) max=curMax;
}
}
return max;
}
01矩阵中最大的全0或全1矩阵
问题描述
给定一个M*N的二维数组，其元素全部由0和1构成，找出最大的全1矩阵，输出这个矩阵的元素个数。
上图中最大全1矩阵就是红色标出的部分，因此输出元素个数6。
求解算法
有了直方图最大矩形面积的基础，这道题就可以拆解为同样的问题来解决：从第一行开始，计算以每一行为底的矩形构成的直方图中最大矩形面积，再在其中找到最大值，就是要求的矩形。
解释一下以每一行为底的矩形构成的直方图，第一行的话，就是这个一维的数组[1,0,1,0,0]，那么直方图显而易见就是这些数值，将这个数组送入上面那个函数，求得最大面积是1；遍历到第二行，此时以第二行为底的矩形是2*5的格式，也就是矩阵的上两行，它可以代表一个直方图的分布，那么这个2*5矩阵的最大全1矩形，就相当于所代表的直方图的最大矩形面积。
因此，需要将这个2*5的矩阵转换成一维数组的形式，也就是计算直方图每个区间有多少个1，而且是连续的1（因为不连续的话就构不成一个子矩阵了），所以对第二行的每个做以下处理：
1、若，那么它的值保持不变还是0，说明当前没有连续的1；
2、若，令
，说明这个区间又多了一个连续的1。
最后第二行得到的数组是[2,0,2,1,1]，将其送入函数，得到最大矩形面积是3；同样的第三行数组是[3,1,3,2,2]，得到最大矩形面积是6；第四行是[4,0,0,3,0]，最大面积为4。遍历结束，得到最终的最大全1矩阵的面积为6。
代码实现
int getMaxRectangle(vector<vector<int>> array){
int m=array.size();
int n=array[0].size();
int max=0;
for (int i=0;i<m;i++){
for (int j=0;j<n;j++){
if (i!=0){
array[i][j]=array[i][j]==0?0:array[i-1][j]+1;
}
}
int curMax=getMaxArea(array[i]);
if (curMax>max) max=curMax;
}
return max;
}
网友评论