Maximal Rectangle

时间：2014-03-31 01:31:41 收藏：0 阅读：673

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

解法1 - 垂线法：
按行遍历整个矩阵，在处理每行的时候用L， R， H三个vector来表示当前行每一点是否在一个合法矩阵内，如果是的话，当前点所在的矩阵的下边延的起始点以及高度各式多少。

通过先从左到右遍历，得到L和H，然后从右向左遍历得到R，并同时可以计算出当前点所在的最大矩阵是多少。更新L,H,R的逻辑在代码中已经很清楚了，大家可以自己在纸上画以下，想一想，这样会理解的更深刻的多。

最后遍历完整个矩阵，我们就得到了最大的合法矩阵是多大了。

解法2：
这个方法按行更新一个vector - p,然后调用 calRect，每次调用calRect实际就是计算一个直方图的最大可能面积（leetcode有另外一题就是专门问这个问题，可以用这个calRect去解决它），而更新p就是更新每次需要计算的直方图的每个横轴点的高度。

这个实现值得看一下的是计算每个直方图最大面积的时候，用了一个stack<pair<int, int>> 在遍历p的时候保存每个点之前的计算信息，从而使得这个calRect的时间复杂度保持在O(N).

class Solution {
public:
    int maximalRectangle(vector<vector<char> > &matrix) {
        int ret = 0;
        int rows = matrix.size();
        if (rows == 0) return 0;
        int cols = matrix[0].size();
        if (cols == 0) return 0;
        
        // 1
        /*
        int L[cols], R[cols], H[cols];
        fill(L, L + cols, 0);
        fill(R, R + cols, cols);
        fill(H, H + cols, 0);
        for (int i = 0; i < rows; i++) {
            int left = 0, right = cols;
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == ‘1‘) {
                    L[j] = max(left, L[j]);
                    H[j]++;
                } else {
                    left = j + 1;
                    L[j] = 0, R[j] = cols, H[j] = 0;
                }
            }
            
            for (int j = cols - 1; j >= 0; j--) {
                if (matrix[i][j] == ‘1‘) {
                    R[j] = min(R[j], right);
                    ret = max(ret, H[j] * (R[j] - L[j]));
                } else {
                    right = j;
                }
            }
        }
        */
        
        vector<int> p(cols, 0);
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == ‘1‘) {
                    p[j] += 1;
                } else {
                    p[j] = 0;
                }
            }
            
            ret = max(ret, calRect(p));
        }
        
        return ret;
    }
    
private:
    int calRect(vector<int> &h) {
        h.push_back(0);
        stack<pair<int, int>> psk;
        int ret = 0;
        for (int i = 0; i < h.size(); i++) {
            int cnt = 0;
            while (!psk.empty() && psk.top().first >= h[i]) {
                cnt += psk.top().second;
                ret = max(ret, psk.top().first * cnt);
                psk.pop();
            }
            
            psk.push(make_pair(h[i], cnt + 1));
        }
        
        h.pop_back();
        return ret;
    }
};

Maximal Rectangle,布布扣,bubuko.com

原文：http://blog.csdn.net/icomputational/article/details/22601765