题目
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。
示例 1:
输入:matrix = [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]]
输出:6
解释:最大矩形如上图所示。
示例 2:
输入:matrix = [[“0”]]
输出:0
示例 3:
输入:matrix = [[“1”]]
输出:1
参数范围:
rows == matrix.length
cols == matrix[0].length
1 <= row, cols <= 200
matrix[i][j] 为 ‘0’ 或 ‘1’
分析
时间复杂度O(n2m)。枚举矩形的left和right,时间复杂度o(n^2)。指定left,right,计算连续1的数量大于等于width的行数,时间复杂度O(m)。
代码
核心代码
class Solution { public: int maximalRectangle(vector<vector<char>>& matrix) { m_r = matrix.size(); m_c = matrix.front().size(); vector<vector<int>> vRightLen(m_r, vector<int>(m_c)); for (int r = 0; r < m_r; r++) { for (int c = m_c - 1; c >= 0; c--) { if ('1' == matrix[r][c]) { vRightLen[r][c] = 1 + ((m_c - 1 == c) ? 0 : vRightLen[r][c + 1]); } } } int iRet = 0; for (int left = 0; left < m_c; left++) { for (int right = left; right < m_c; right++) { const int width = right - left + 1; int height = 0; for (int r = 0; r < m_r; r++) { if (vRightLen[r][left] < width) { iRet = max(iRet, height * width); height = 0; } else { height++; } } iRet = max(iRet, height * width); } } return iRet; } int m_r, m_c; };
测试用例
template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { assert(v1[i] == v2[i]); } } template<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } int main() { vector<vector<char>> matrix; int r; { Solution slu; matrix = { {'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'} }; auto res = slu.maximalRectangle(matrix); Assert(6, res); } { Solution slu; matrix = { {'0'} }; auto res = slu.maximalRectangle(matrix); Assert(0, res); } { Solution slu; matrix = { {'1'} }; auto res = slu.maximalRectangle(matrix); Assert(1, res); } { Solution slu; matrix = { {'1','1'}}; auto res = slu.maximalRectangle(matrix); Assert(2, res); } { Solution slu; matrix = { {'1'},{'1' } }; auto res = slu.maximalRectangle(matrix); Assert(2, res); } }
单调栈
枚举底部,本题就可以转化成柱形图的最大矩形
class Solution { public: int maximalRectangle(vector<vector<char>>& matrix) { m_c = matrix.front().size(); vector<int> vHeights(m_c); int iRet = 0; for (int r = 0; r < matrix.size(); r++) { for (int c = m_c - 1; c >= 0; c--) { if ('1' == matrix[r][c]) { vHeights[c] +=1 ; } else { vHeights[c] = 0 ; } } iRet = max(iRet, largestRectangleArea(vHeights)); } return iRet; } int largestRectangleArea(vector<int>& heights) { m_c = heights.size(); vector<pair<int, int>> vLeftHeightIndex; vector<int> vLeftFirstLess(m_c, -1), vRightFirstMoreEqual(m_c, m_c);//别忘记初始化 for (int i = 0; i < m_c; i++) { while (vLeftHeightIndex.size() && (heights[i] <= vLeftHeightIndex.back().first)) { vRightFirstMoreEqual[vLeftHeightIndex.back().second] = i; vLeftHeightIndex.pop_back(); } if (vLeftHeightIndex.size()) { vLeftFirstLess[i] = vLeftHeightIndex.back().second; } vLeftHeightIndex.emplace_back(heights[i], i); } int iRet = 0; for (int i = 0; i < m_c; i++) { iRet = max(iRet, heights[i] * (vRightFirstMoreEqual[i] - vLeftFirstLess[i] - 1)); } return iRet; } int m_c; };
2022年12月版代码
class Solution { public: int maximalRectangle(vector<vector<char>>& matrix) { m_r = matrix.size(); m_c = matrix[0].size(); vector<vector<int>> leftNums; leftNums.assign(m_r, vector<int>(m_c)); for (int r = 0; r < m_r; r++) { for (int c = 0; c < m_c; c++) { if ('0' == matrix[r][c]) { leftNums[r][c] = 0; } else { leftNums[r][c] = 1 + ((c > 0) ? leftNums[r][c - 1] : 0); } } } for (int c = 0; c < m_c; c++) { stack<pair<int, int>> sta; for (int r = 0; r < m_r; r++) { int iMinR = r; while (sta.size() && (sta.top().first > leftNums[r][c])) { PopStack(sta, iMinR, r); } if (sta.empty() || (sta.top().first < leftNums[r][c])) { sta.emplace(leftNums[r][c], iMinR); } } while (sta.size()) { int iMinR = m_r; PopStack(sta, iMinR, m_r); } } return m_iMaxArea; } void PopStack(stack<pair<int, int>>& sta,int& iMinRow,int r ) { int iWidth = sta.top().first; iMinRow = sta.top().second; sta.pop(); m_iMaxArea = max(m_iMaxArea, iWidth*(r - 1 - iMinRow + 1)); } int m_r, m_c; int m_iMaxArea = 0; };
扩展阅读
视频课程
有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 ||-|
|闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。|
| 子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |
|如果程序是一条龙,那算法就是他的是睛|
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。