首页 > 代码库 > [leetcode]
[leetcode]
问题描述:
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思想类似,只是对每行都执行了一遍。
代码:
int maximalRectangle(vector<vector<char> > &matrix) { //C++ if(matrix.size() == 0|| matrix[0].size()==0) return 0; int rows = matrix.size(); int cols = matrix[0].size(); vector<int> H(cols+1); H[cols] = 0; int max = 0; for(int i = 0; i < rows; i++) { for(int j=0; j<cols; j++) if(matrix[i][j]=='1') H[j]++; else H[j]=0; vector<int> stack; for(int j = 0; j<cols+1; j++) { while(stack.size() >0&&H[stack.back()]>H[j]) { int h = H[stack.back()]; stack.pop_back(); int left = stack.size()>0?stack.back():-1; if(h*(j-1-left)>max) max = h*(j-1-left); } stack.push_back(j); } } return max; }
[leetcode]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。