首页 > 代码库 > Leetcode:Maximal Rectangle 最大全1子矩阵
Leetcode:Maximal Rectangle 最大全1子矩阵
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.
解题分析:
联想到 最大矩形面积 这一题,可以在O(n)时间内求出 最大的矩形面积
如果我们把每一行看成x坐标,那高度就是从那一行开始往上数的1的个数。
利用 最大矩形面积 的方法,在O(n2)时间内就可以求出每一行形成的“柱状图”的最大矩形面积了
class Solution {public: int maximalRectangle(vector<vector<char> > &matrix) { int nRow = matrix.size(); if (nRow == 0) return 0; int nCol = matrix.at(0).size(); std::vector<int> tmp(nCol, 0); int result = 0; for (int i = 0; i < nRow; ++i) { // 计算每一行可以形成的最大矩形面积 for (int j = 0; j < nCol; ++j) { if (matrix.at(i).at(j) == ‘0‘) { tmp.at(j) = 0; } else { tmp.at(j)++; // 计算当前行的当前列的累积高度(1的个数) } } int area = largestRectangleArea(tmp); result = std::max(result, area); } return result; } // 最大矩形面积 int largestRectangleArea(std::vector<int>& height) { if (height.size() == 0) return 0; height.push_back(-1); std::stack<int> stk; int result = 0; for (int i = 0; i < height.size(); ) { if (stk.empty() || height.at(i) > height.at(stk.top())) { stk.push(i); ++i; } else { int idx = stk.top(); stk.pop(); int area = height.at(idx) * (stk.empty() ? i : i - stk.top() - 1); result = std::max(result, area); } } return result; }};
Leetcode:Maximal Rectangle 最大全1子矩阵
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。