[LeetCode] 01矩阵中最大矩形 Maximal Rectangle

相关问题1：[LeetCode] Find max subsquare whose border values are all 1

相关问题2：[LeetCode] 01矩阵中最大正方形 Maximal Square

在一个M * N的矩阵中，所有的元素只有0和1， 找出只包含1的最大矩形。

例如：图中是一个４　×　６的矩形，画出红色的是我们要找到的区域。

仔细观察发现：因为我们要找的是矩形，所以它一定是以 某个行元素开始的，这样的话，其实我们要找到的某个矩形就转换成 一某一个行开始的 histogram的最大矩形问题了。

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

第一行表示，我们以第一行作为底边，所形成的 histogram的高度，其他行也类似。所以问题变成了 枚举每一行，然后求出每一行对应的histogram的最大矩形。利用单调栈求histogram的最大矩形可以参考：http://blog.csdn.net/jiyanfeng1/article/details/8067265

代码如下：

    int maximalRectangle(vector<vector<char> > &matrix) {
    // max rectangle in a 0-1 matrix
    
        if(matrix.size()==0) return 0;
        
        int* hist = new int[matrix[0].size()];
        memset(hist, 0, sizeof(int)*matrix[0].size());
        
        int max_ = 0;
        
        for(int i=0; i<matrix.size(); i++)
        {
            for(int j=0; j<matrix[0].size(); j++)
            {
                if(matrix[i][j]=='1')
                    *(hist+j) += 1;
                else
                    *(hist+j) = 0;
            }
            
            max_ = max(max_, maxRectInHistogram(hist, matrix[0].size()) );
        }
        
        return max_;
    }
    
    int maxRectInHistogram(int hist[], int n)  
    // hist: contains the heights of the bars   
    // n: the number of the bars in the histogram.  
    {  
            int* arr = new int[n];// 申请一个额外的数组  
            arr[0] = hist[0];  
            int max = hist[0]; // 最大面积  
      
            for(int i=1; i<n; i++)  
            {  
                    arr[i] = hist[i];  
                    for(int j=i-1; j>=0; j--)  
                            if(arr[j]>arr[i]){  
                                    if(arr[j]*(i-j)>max)  
                                            max = arr[j]*(i-j);  
                                    arr[j] = arr[i];  
                            }  
                            else break;  
                    //数组arr里的元素，保持非递减的顺序。  
            }  
      
            //重新扫描一边，以更新最大面积  
            for(int i=0; i<n; i++)  
                    if(arr[i]*(n-i)>max)  
                            max = arr[i]*(n-i);  
            return max;  
    }