首页 > 代码库 > [LeetCode] Maximal Rectangle（good）
[LeetCode] Maximal Rectangle（good）
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”这个题的解法，思想差不多一样，只是用h向量表示Rectangle中此元素中第一行到本行的高度，非常妙的算法：
class Solution {public: int maximalRectangle(vector<vector<char> > &matrix) { if(matrix.size() == 0 || matrix[0].size() == 0) return 0; int cLen = matrix[0].size(); int rLen = matrix.size(); //height array vector<int> h(cLen+1,0); int max = 0; for(int row = 0;row<rLen;row++){//for(1) stack<int> s; for(int i=0;i<cLen+1;i++){//for(2) if(i<cLen){ if(matrix[row][i]==‘1‘) h[i] += 1; else h[i] = 0; }//end if if(s.empty() || h[s.top()]<=h[i]){ s.push(i); }else{ while(!s.empty() && h[i]<h[s.top()]){ int top = s.top(); s.pop(); int area = h[top]*(s.empty()?i:(i-s.top()-1)); if(area > max) max = area; }//end while s.push(i); }//end if }//end for(2) }//end for(1) return max; }//end func};
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。