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
AC code:
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int row = matrix.size();
if (row == 0) return 0;
int col = matrix[0].size();
int res = 0;
vector<int> height(col, 0);
vector<int> left(col, 0);
vector<int> right(col, col);
for (int i = 0; i < row; ++i) {
int curLeft = 0, curRight = col;
for (int j = 0; j < col; ++j) {
if (matrix[i][j] == '1')
height[j]++;
else
height[j] = 0;
}
for (int j = 0; j < col; ++j) {
if (matrix[i][j] == '1')
left[j] = max(left[j], curLeft);
else {
left[j] = 0;
curLeft = j + 1;
}
}
for (int j = col-1; j >= 0; --j) {
if (matrix[i][j] == '1')
right[j] = min(right[j], curRight);
else {
right[j] = col;
curRight = j;
}
}
for (int j = 0; j < col; ++j) {
res = max(res, height[j] * (right[j] - left[j]));
}
}
return res;
}
};
Runtime: 12 ms, faster than 98.86% of C++ online submissions for Maximal Rectangle.
写成了：
vector<int> height(0, col);
导致数组出界所以一直报错。初始化vector的时候 vector<int> height(arg1, arg2);
arg1代表数组的长度， arg2代表数组的值。
题解：
这道题的关键是left, right, height这三个数组。
left： 代表从左往右连续为1的第一个1的下标最大值；
right： 代表从右往左连续为1的第一个1的下标最小值；
height： 代表从上往下连续为1的个数；
举个栗子：
TestCase：
[ ["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"] ]
height：
1 0 1 0 0
2 0 2 1 1
3 1 3 2 2
4 0 0 3 0
left:
0 0 2 0 0
0 0 2 2 2
0 0 2 2 2
0 0 0 3 0
right:
1 5 3 5 5
1 5 3 5 5
1 5 3 5 5
1 5 5 4 5
面积的计算公式：
res = max(res, height[j] * (right[j] - left[j]);
2.
AC code:
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int row = matrix.size();
if (row == 0) return 0;
int col = matrix[0].size();
int res = 0;
vector<int> height(col+1, 0);
height[col] = 0;
for (int i = 0; i < row; ++i) {
stack<int> s;
for (int j = 0; j <= col; ++j) {
if (j < col) {
if (matrix[i][j] == '1') height[j]++;
else height[j] = 0;
}
if (s.empty() || height[s.top()] <= height[j])
s.push(j);
else {
while (!s.empty() && height[s.top()] > height[j]) {
int h = height[s.top()];
s.pop();
int cur = h * (s.empty() ? j : (j-s.top()-1));
res = max(res, cur);
}
s.push(j);
}
}
}
return res;
}
};
Runtime: 16 ms, faster than 69.64% of C++ online submissions for Maximal Rectangle.
这种方法的思想和84题有些相似的地方，height代表矩形的高度，stack中存储递增的数据，当遇到小于前面的数据时，开始计算，最大的矩形面积。