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.

 

这题的思路完全来源，不过要对原始数据做一个处理，把每行处理成直方图形式的数据。然后调用直方图的算法就可以了，所以你的先明白直方图最大面积计算方法。时间复杂度O(n^2)。

输入的矩阵

转换后的矩阵

1 class Solution { 2 public: 3     int largestRectangleArea(vector
     
      & height) { 4         int result=0; 5         height.push_back(0); 6         stack
      
        mystack; 7         for(int i=0;i
       
        >& matrix) {26         if(matrix.size()==0 || matrix[0].size()==0) return 0;27         int result=0;28         vector
        
         
          > histogram;29         int rows = matrix.size();30         int cols = matrix[0].size();31         vector
          
            height_row(cols,0);32 for(int i=0;i
           
            result?maxArea:result;51 }52 return result;53 }54 };
           
          
         
        
       
      
     

 其实不需要把整个直方图矩阵得到后再计算，得到每行的直方图举证就可以计算了。

1 class Solution { 2 public: 3     int largestRectangleArea(vector
     
      & height) { 4         int result=0; 5         height.push_back(0); 6         stack
      
        mystack; 7         for(int i=0;i
       
        >& matrix) {26         if(matrix.size()==0 || matrix[0].size()==0) return 0;27         int result=0;28         int rows = matrix.size();29         int cols = matrix[0].size();30         vector
        
          height_row(cols,0);31         for(int i=0;i
         
          result?maxArea:result;46         }47         return result;48     }49 };