[LeetCode] Maximal Rectangle

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

在做Largest Rectangle in Histogram的时候有人说可以用在这题，看了一下还真是，以每行为x轴，每列往上累计的连续的1当成高度，就可以完全使用一样的方法了。

 int largestArea(vector<int>height){

     stack<int> s;

     int maxArea = ;

     int i = ;

     height.push_back();

     int len = height.size();

     while (i < len){

         if (s.empty() || height[s.top()] < height[i]){

             s.push(i++);

         }else{

             int t = s.top();

             s.pop();

             maxArea = max(maxArea, height[t] * (s.empty()? i : (i-s.top()-)));

         }

     }

     return maxArea;

 }

 int maximalRectangle(vector<vector<char>> &matrix){

     vector<int> height;

     int maxRect=;

     for (int row=; row<matrix.size(); row++){

         for (int col=; col<matrix[row].size(); col++){

             if (matrix[row][col] == ''){

                 height.push_back();

             }

             else{

                 int c=;

                 for (int i=row; i>-; i--){

                     if (matrix[i][col] != ''){

                         c++;

                     }else {

                         break;

                     }

                 }

                 height.push_back(c);

             }

         }

         for (int i=;i<height.size(); i++){

             cout << height[i] << " ";

         }

         cout << endl;

         maxRect = max(maxRect, largestArea(height));

         height.clear();

     }

     return maxRect;

 }

 int maximalRectangle2(vector<vector<char>> &matrix){

     int maxRect = ;

     if (matrix.size() < ) return ;

     vector<int>height(matrix[].size(), );

     for (int i=; i<matrix.size(); i++){

         for (int j=; j<matrix[i].size(); j++){

             if (matrix[i][j] == ''){

                 height[j] += ;

             }else{

                 height[j] = ;

             }

         }

         maxRect = max(maxRect, largestArea(height));

     }

     return maxRect;

 }

第一个maximalRectangle函数我用了很蠢的遍历方法来获得每行的height，这样活生生的把原本O(n^2)搞成了O(n^3)。。。最后看了别人博客，说height是可以通过前一行的值算出了的(有点类似DP的思想...如果这也算的话)，豁然开朗，才写出了

maximalRectangle2这个真正的O(n^2)方法。

巴特西

[LeetCode] Maximal Rectangle

最新文章

热门文章