第一种方法是利用DP。时间复杂度是 O(m * m * n)

dp(i,j)：矩阵中同一行以(i,j)结尾的所有为1的最长子串长度

代码例如以下：

int maximalRectangle(vector
     
      
        > &matrix) {        int m = matrix.size();        if (m == 0) return 0;        int n = matrix[0].size();        if (n == 0) return 0;        vector
       
        
         > dp(m, vector
         
          (n));        int maxArea = 0;        for (int i = 0; i < m; i++)        {            for (int j = 0; j < n; j++)            {                if (matrix[i][j] == '0') continue;                dp[i][j] = (j == 0 ? 1 : dp[i][j - 1] + 1);                int minX = dp[i][j];                for (int k = 1; k <= i + 1; k++)                {                    minX = min(minX, dp[i - k + 1][j]);                    maxArea = max(maxArea, minX * k);                }            }        }        return maxArea;    }
         
        
       
      
     

另外一种方法：

来自https://oj.leetcode.com/discuss/5198/a-o-n-2-solution-based-on-largest-rectangle-in-histogram

事实上这里和 Largest Rectangle in Histogram是类似的，

之前的dp(i,j)保存以第i行。第j列结尾的，同一行中连续1的个数；那么这里我们用一个数组x，使x[j]保存当前行第j列中的连续1的个数。之后按行遍历，每一行都按Largest Rectangle in Histogram的算法处理一遍

代码例如以下：复杂度为O(m*n)

int maximalRectangle(vector
     
      
        > &matrix) {        int m = matrix.size();        if (m == 0) return 0;        int n = matrix[0].size();        if (n == 0) return 0;        vector
       
         height(n);        int maxArea = 0;        for (int i = 0; i < m; i++)        {            vector
        
          index;            for (int j = 0; j < n; j++)            {                if (matrix[i][j] == '0') height[j] = 0;                else height[j] ++;                while (index.size() && height[j] <= height[index.back()])                    maxArea = max(getArea(height, index, j), maxArea);                index.push_back(j);            }            while (index.size())                maxArea = max(getArea(height, index, height.size()), maxArea);        }        return maxArea;    }        int getArea(vector
         
           &height, vector
          
           & index, int start) { int areaH = height[index.back()]; index.pop_back(); int end = index.empty() ? -1 : index.back(); return (start - end - 1) * areaH; }
          
         
        
       
      
     

第三种方法：

利用极值http://hi.baidu.com/mzry1992/item/030f9740e0475ef7dc0f6cba

H[i][j] = 0                    matrix[i][j] = '0'

            H[i-1][j] + 1     matrix[i][j] = '1'

L[i][j] = max{L[i-1][j], 第i行左边第一个'0'的位置+1}

R[i][j] = min{R[i-1][j], 第i行右边第一个'0'的位置-1}

maxArea = max{maxArea, H[i][j] * (R[i][j] - L[i][j] + 1)}

因为H，L，R均仅仅用到i-1,j的内容，能够将空间进一步压缩成为O(N)的

代码例如以下：

int maximalRectangle(vector
     
      
        > &matrix) {        int m = matrix.size();        if (m == 0) return 0;        int n = matrix[0].size();        if (n == 0) return 0;        vector
       
         h(n);        vector
        
          l(n);        vector
         
           r(n, n - 1);        int maxArea = 0, maxL = 0, minR = m - 1;        for (int i = 0; i < m; i++)        {            maxL = 0, minR = n-1;            for (int j = 0; j < n; j++)            {                if (matrix[i][j] == '0')                {                    h[j] = 0;                    l[j] = 0;                    r[j] = n - 1;                    maxL = j + 1;                }                else                {                    h[j]++;                    l[j] = max(l[j], maxL);                }            }                        for (int j = n - 1; j >= 0; j--)            {                if (matrix[i][j] == '0')                {                    r[j] = n - 1;                    minR = j - 1;                }                else                {                    r[j] = min(r[j], minR);                    maxArea = max(maxArea, h[j] * (r[j] - l[j] + 1));                }            }        }        return maxArea;    }