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

方法一

最直观也是最naive的思路：以任意两点（ib, jb), (ie, je)为两对角顶点，查看是否包含为0的元素。O(n^6),提交会TLE

方法二

任意选取一点(ib, jb)作为左上角，从ib行开始逐行寻找在该行下最右可达位置，width[i] <= width[i-1]。O(n^4)。提交能够通过，但是所用时间较长。参见这里。

class Solution {
public:

    int maximalRectangle(vector<vector<char> > &matrix) {
        if (matrix.empty())
            return 0;
        int maxR = 0;
        int m = matrix.size();
        int n = matrix.front().size();
        for (int ib=0; ib<m; ib++)
            for (int jb=0; jb<n; jb++)
            {
                int prevJE = n-1;
                for (int ie=ib; ie<m; ie++)
                {
                    int je = jb;
                    while (je <= prevJE && matrix[ie][je] == '1')
                        je++;
                    je--;
                    prevJE = je;
                    int area = (je - jb + 1) *(ie - ib + 1);
                    maxR = max(area, maxR);
                }
            }

        return maxR;
    }
};

 

方法三

选取一行ib作为上边，对每一列计算可达(‘1’)的最大深度(O(n^2))，则可以得到一个以ib行为横坐标的histogram，然后参考Largest Rectangle in Histogram的O(n)解法，可以得到O(n *(n^2+ n)) = O(n^3)的解法

方法四

方法三中每到新的一行，都需要计算新的可达深度，花费O(n^2)，而相邻两行之间的深度应该是相关的。所以可以在最开始计算一次深度，之后只在深度小于0（代表之前找到的‘0’值在此行之上）时才重新计算深度。深度计算过程中，矩阵所有元素访问一遍，总体时间复杂度为O(n^2)，再加上n行的histogram，总的时间复杂度为O(n^2)，空间复杂度O(n)

class Solution {
public:

    int maxInHist(vector<int> ht)
    {
        int maxR = 0;
        ht.push_back(0);
        vector<int> left;
        for (int i=0; i<ht.size(); i++)
        {
            while (!left.empty() && ht[left.back()] > ht[i])
            {
                int h = ht[left.back()];
                left.pop_back();
                int l = left.empty() ? -1 : left.back();
                maxR = max(maxR, h *(i - l - 1));
            }
            left.push_back(i);
        }
        return maxR;
    }

    int depth(vector<vector<char> > & matrix, int x, int y)
    {
        int k = 0;
        while (x + k < matrix.size() && matrix[x + k][y] == '1')
            k++;
        return k;
    }

    int maximalRectangle(vector<vector<char> > &matrix) {
        if (matrix.empty())
            return 0;
        int maxR = 0;
        int m = matrix.size();
        int n = matrix.front().size();
        vector<int> ht(n, 0);
        for (int i=0; i<m; i++)
        {
            for (int j=0; j<n; j++)
                if (--ht[j] < 0)
                    ht[j] = depth(matrix, i, j);
            maxR = max(maxR, maxInHist(ht));
        }

        return maxR;
    }
};

除此之外，这题还有其他解法：

方法五：固定两边，逐行查找是否包含‘0’，包含的标记为可选上下界，然后按顺序计算上下界之间的各个区域面积。O(n^4)

这里还有其他思路可供参考。leetcode discussion中提供的悬线(dangling line)方案从这里参考而来，但是感觉实质和histogram类似，实现则更为复杂。

经验教训：

• 少年不要轻易放弃治疗。。。仔细思考的话，即使不能做到O(n^2)， O(n^4)还是有很清晰的思路的，怎么就选了最naive的方法呢。。。
• 和largest rectangle in histogram 一题类似，区域的边界是思考入手的地方。对于这种有很多可能性的问题，需要先固定一些维度，再去考虑其他维度。这一题里，四条边和两个对角顶点都是可以选取的固定对象。可以先固定两条边（方法五， 方法二， 普通方法），可以先固定一条边（方法四， 文艺方法），至于方法一这种固定顶点固定四条边自带O(n^4)复杂度的，就是出来卖萌送一血的2B方法了。
• 难题多思考思考，有益身体健康。套路很可怕