首页 > 代码库 > Maximal Rectangle
Maximal Rectangle
求一个01二位数组最大的矩阵,把它化为直角图再一行一行地算
class Solution{ public: int maximalRectangle(vector<vector<char> > &martix){ if(martix.size() == 0 || martix[0].size() == 0) return 0; int height[1000][1000]; int maxx = -1; int row = martix.size(); int col = martix[0].size(); for(int j =0; j < col; j++) for(int i = 0; i < row; i++){ if(martix[i][j] == '0') height[i][j] = 0; else if(i == 0) height[0][j] = 1; else height[i][j] = height[i-1][j]+1; } stack<int>s; for(int i = 0; i < row; ++i){ for(int j = 0; j < col; ++j){ if(s.empty()) s.push(j); else { while(!s.empty() && height[i][s.top()] > height[i][j]){ int tmp = s.top(); s.pop(); maxx = max(maxx,(s.empty()?j:(j-s.top()-1))*height[i][tmp]); } s.push(j); } } while(!s.empty()){ int tmp = s.top(); s.pop(); maxx = max(maxx,(s.empty()?col:(col-s.top()-1))*height[i][tmp]); } } return maxx; } };
Maximal Rectangle
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。