首页 > 代码库 > Maximal Rectangle
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.
思路：参见《浅谈用极大化思想解决最大子矩形问题》。这道题我不会，还是贴代码吧。
class Solution {public: int maximalRectangle( vector<vector<char>> &matrix ) { if( matrix.empty() ) { return 0; } int n = matrix[0].size(); vector<int> H( n, 0 ); vector<int> L( n, 0 ); vector<int> R( n, n ); int ret = 0; for( int i = 0; i < matrix.size(); ++i ) { int left = 0, right = n; for( int j = 0; j < n; ++j ) { if( matrix[i][j] == ‘0‘ ) { H[j] = 0; L[j] = 0; R[j] = n; left = j+1; } else { ++H[j]; L[j] = max( L[j], left ); } } for( int j = n-1; j >= 0; --j ) { if( matrix[i][j] == ‘0‘ ) { right = j; } else { R[j] = min( R[j], right ); ret = max( ret, (R[j]-L[j])*H[j] ); } } } return ret; }};
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。