leetcode:Maximal Rectangle

超、凢脫俗 2022-08-08 09:19 139阅读 0赞

这是leetcode的第85题，原题如下：

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and return its area.

leetcode的第84题是Largest Rectangle in Histogram，原题如下：  
![这里写图片描述][20150514111157706]  
[解决方案][Link 1]在[http://blog.csdn.net/u010902721/article/details/45718007][Link 1]。

# 思路 #

之所以把84题放在这里，是想利用84题的解题方案。下面看一下84题和本题的联系。  
一个case：  
![例子][20150514122738544]  
分别求第一行、上面两行、上面三行、上面四行、上面五行中矩形的最大面积，这5个最大面积中最大的一个就是最终结果。

因为求的是矩形的面积，所以计算高度的时候应该从该元素往上遍历，遇到第一个非’1’字符的时候就停止。对于这个例子，结果是这样子的。

height0\[\] = \{0,0,1,1,0,0\}; //第一行  
height1\[\] = \{1,1,2,0,0,0\}; //上面两行  
height2\[\] = \{0,2,3,1,0,0\}; //上面三行  
height3\[\] = \{0,0,4,0,1,1\}; //上面四行  
height4\[\] = \{0,0,5,1,2,2\}; //上面五行

将height0到height4这五个数组放到84题的解决方案中算出最大值，然后将这5个最大值中的最大值作为最终结果。

# 代码 #

class Solution {
    public:
    //===------------------------------------------
    //84题的解决方案，直接copy过来
    //===------------------------------------------
    int largestRectangleArea(vector<int> &height) {
         int n = height.size();
         if(n == 0)
            return 0;
        if(n == 1)
            return height[0];
         int *left = new int[n], *right = new int[n];
         left[0] = -1;
         right[n - 1] = n;
         for(int i = 1; i < n; i++){
             int j = i-1;
             int k = n-i;
             while(height[i] <= height[j] && j != -1)
                j = left[j];
             while(height[n-i-1] <= height[k] && k != n)
                k = right[k];
            left[i] = j;
            right[n-i-1] = k;
         }
         int area, max_area = 0;
         for(int i = 0; i < n; i++){
             area = (right[i] - left[i] - 1) * height[i];
             max_area = max(max_area, area);
         }
         return max_area;
     }
     //===------------------------------------------
    //本题的解决方案
    //===------------------------------------------
        int maximalRectangle(vector<vector<char> >& matrix) {
            int m = matrix.size();
            if(m == 0)
                return 0;
            int n = matrix[0].size();
    
            vector<int> v;
            int height = 0;
            int max_area = 0;
            for(int i = 0; i < m; i++){
                v.clear();
                for(int j = 0; j < n; j++){
                    height = 0;
                    for(int t = i; t >= 0; t--){
                        if(matrix[t][j] == '1')
                            height += 1;
                        else
                            break;
                    }
                    v.push_back(height);
                }
                max_area = max(max_area, largestRectangleArea(v));
            }
            return max_area;
        }
    };

[20150514111157706]: /images/20220805/b5a40b49d414422983ceb6884601058e.png
[Link 1]: http://blog.csdn.net/u010902721/article/details/45718007
[20150514122738544]: /images/20220805/34d3bc8fd0b743eb81bab8421dd6b013.png