leetcode
程序员文章站
2022-07-06 19:55:39
...
Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.
Example:
Input:
[
[“1”,“0”,“1”,“0”,“0”],
[“1”,“0”,“1”,“1”,“1”],
[“1”,“1”,“1”,“1”,“1”],
[“1”,“0”,“0”,“1”,“0”]
]
Output: 6
class Solution {
public:
int maximalRectangle(vector<vector<char>> &matrix) {
if (matrix.size() == 0)
return 0;
int n = matrix.size(), m = matrix[0].size(), sum = 0;
vector<int> height(m, 0), right(m, m), left(m, 0);
for (int i = 0; i < n; i++) {
int cur_left = 0, cur_right = m;
for (int j = 0; j < m; j++) {
if (matrix[i][j] == '1')
height[j]++;
else
height[j] = 0;
}
for (int j = 0; j < m; j++) {
if (matrix[i][j] == '1') {
left[j] = max(left[j], cur_left);
} else {
left[j] = 0, cur_left = j + 1;
}
}
for (int j = m - 1; j >= 0; --j) {
if (matrix[i][j] == '1') {
right[j] = min(right[j], cur_right);
} else {
right[j] = m, cur_right = j;
}
}
for (int j = 0; j < m; j++) {
sum = max(sum, (right[j] - left[j]) * height[j]);
}
}
return sum;
}
};
上一篇: 在CentOS中升级gcc4.8到gcc5并修改默认设置
下一篇: Xbunder