欢迎访问LeetCode题解合集
题目描述
给定一个仅包含 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
示例 3:
输入:matrix = [["0"]]
输出:0
示例 4:
输入:matrix = [["1"]]
输出:1
示例 5:
输入:matrix = [["0","0"]]
输出:0
提示:
-
rows == matrix.length
-
cols == matrix[0].length
-
$0 \le row, cols \le 200$
-
matrix[i][j]
为'0'
或'1'
题解:
统计每一层当前位置 (i,j)
上方有多少个连续的 1
,问题转换成求每层的最大矩形面积,使用单调栈即可,参考 柱状图中最大的矩形 。
时间复杂度:$O(n*m)$
额外空间复杂度:$O(m)$
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int n = matrix.size();
if ( !n ) return 0;
int m = matrix[0].size();
if ( !m ) return 0;
vector<int> f(m + 1);
f[m] = -1;
vector<int> stk;
int top, gap;
int ret = 0;
for ( int i = 0; i < n; ++i ) {
for ( int j = 0; j < m; ++j ) {
if ( !i ) f[j] = matrix[i][j] & 15;
else {
if ( matrix[i][j] == '1' ) f[j] += 1;
else f[j] = 0;
}
}
stk.clear();
for ( int i = 0; i <= m; ++i ) {
while ( stk.size() && f[stk.back()] > f[i] ) {
top = stk.back();
stk.pop_back();
if ( stk.size() ) gap = i - stk.back() - 1;
else gap = i;
ret = max( ret, gap * f[top] );
}
stk.push_back( i );
}
}
return ret;
}
};
/*
时间:36ms,击败:96.25%
内存:10.8MB,击败:99.07%
*/