首页 > 代码库 > Leetcode Maximal Rectangle

Leetcode Maximal Rectangle

2024-07-09 16:12:21   229人阅读

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^3)，最大全1子矩阵，利用直方图求解，可以参考对最大全零子矩阵的研究

class Solution {public:    int maximalRectangle(vector<vector<char> > &matrix) {        if(matrix.empty()) return 0;        int w = matrix[0].size(),h = matrix.size(), res = 0;        for(int i = 0 ; i < w; ++ i){            char row[h];            for(int j =  i ; j < w; ++ j){                if( j == i ){                    for(int k = 0 ; k <  h; ++ k){                        row[k] = matrix[k][i];                    }                }else{                    for(int k = 0 ; k < h; ++ k){                        if(matrix[k][j]!=matrix[k][j-1]) row[k]=‘X‘;                    }                                    }                int cnt = 0 ,maxCnt = 0;                for(int k = 0 ; k < h ; ++ k){                    if(row[k] == ‘X‘ || row[k] == ‘0‘) cnt = 0;                    else if((cnt > 0) && row[k]==row[k-1] ){                        cnt++;                    }else cnt = 1;                    maxCnt = max(maxCnt, cnt);                }                res = max(res,maxCnt*(j-i+1));            }        }        return res;    }};

 


联系
我们