首页 > 代码库 > 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.
参考：http://xpentium.blog.163.com/blog/static/22737815020147795123240/
题目是说matrix中的元素可能有0和1，找出一个子矩阵，这个子矩阵要求是全为1中最大的。如果暴力求解的话，复杂度将直逼O(n^4)。
这有了第一道题的铺垫后，第二道题目就简单了，经过一些变换后，两道题目可以看成等价的。转化的方法是把矩阵中的元素[i][j]的值重置为从[0][j]到[i][j]中在[i][j]之前连续1的个数。
例子中矩阵将变成
0 0 1 0
0 0 0 1
0 1 1 2
0 0 2 3
然后怎么办呢，每一行不就变成了这一行上方的直方图了吗？直接调用上题的解法就OK了，时间复杂度O(n^2)、
C++实现代码：
#include<iostream>#include<vector>#include<stack>using namespace std;class Solution{public: int maximalRectangle(vector<vector<char> > &matrix) { if(matrix.empty()||matrix[0].empty()) return 0; int row=matrix.size(); int col=matrix[0].size(); int i,j; vector<vector<int> > heights(row,vector<int>(col)); int ret=0; for(j=0; j<col; j++) heights[0][j]=matrix[0][j]==‘1‘?1:0; for(i=1; i<row; i++) { for(j=0; j<col; j++) { if(matrix[i][j]==‘0‘) heights[i][j]=0; else heights[i][j]=heights[i-1][j]+1; } } for(i=0; i<row; i++) { int area=largestRectangleArea(heights[i]); ret=max(ret,area); } return ret; } int largestRectangleArea(vector<int> &height) { if(height.empty()) return 0; int i,j; int minH; int maxArea=0; int n=height.size(); for(i=0; i<n; i++) { minH=height[i]; for(j=i; j<n; j++) { minH=min(minH,height[j]); maxArea=max(maxArea,minH*(j-i+1)); } } return maxArea; }};int main(){ Solution s; vector<vector<char> > ch={{‘0‘,‘0‘,‘1‘,‘0‘},{‘0‘,‘0‘,‘0‘,‘1‘},{‘0‘,‘1‘,‘1‘,‘1‘},{‘0‘,‘0‘,‘1‘,‘1‘}}; cout<<s.maximalRectangle(ch)<<endl;}
Maximal Rectangle
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。