# C++实现LeetCode(85.最大矩形)

## [LeetCode] 85. Maximal Rectangle 最大矩形

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 > &matrix) {
int res = 0;
vector height;
for (int i = 0; i < matrix.size(); ++i) {
height.resize(matrix[i].size());
for (int j = 0; j < matrix[i].size(); ++j) {
height[j] = matrix[i][j] == '0' ? 0 : (1 + height[j]);
}
res = max(res, largestRectangleArea(height));
}
return res;
}
int largestRectangleArea(vector& height) {
int res = 0;
stack s;
height.push_back(0);
for (int i = 0; i < height.size(); ++i) {
if (s.empty() || height[s.top()] <= height[i]) s.push(i);
else {
int tmp = s.top(); s.pop();
res = max(res, height[tmp] * (s.empty() ? i : (i - s.top() - 1)));
--i;
}
}
return res;
}
};```

```class Solution {
public:
int maximalRectangle(vector>& matrix) {
if (matrix.empty() || matrix[0].empty()) return 0;
int res = 0, m = matrix.size(), n = matrix[0].size();
vector height(n + 1);
for (int i = 0; i < m; ++i) {
stack s;
for (int j = 0; j < n + 1; ++j) {
if (j < n) {
height[j] = matrix[i][j] == '1' ? height[j] + 1 : 0;
}
while (!s.empty() && height[s.top()] >= height[j]) {
int cur = s.top(); s.pop();
res = max(res, height[cur] * (s.empty() ? j : (j - s.top() - 1)));
}
s.push(j);
}
}
return res;
}
};```

[ [ 1 , 1 , 0 , 0 , 1 ], [ 0 , 1 , 0 , 0 , 1 ], [ 0 , 0 , 1 , 1 , 1 ], [ 0 , 0 , 1 , 1 , 1 ], [ 0 , 0 , 0 , 0 , 1 ] ]

h: 1 1 0 0 1

l: 0 0 0 0 4

r: 2 2 5 5 5

h: 0 2 0 0 2

l: 0 1 0 0 4

r: 5 2 5 5 5

h: 0 0 1 1 3

l: 0 0 2 2 4

r: 5 5 5 5 5

h: 0 0 2 2 4

l: 0 0 2 2 4

r: 5 5 5 5 5

h: 0 0 0 0 5

l: 0 0 0 0 4

r: 5 5 5 5 5

```class Solution {
public:
int maximalRectangle(vector>& matrix) {
if (matrix.empty() || matrix[0].empty()) return 0;
int res = 0, m = matrix.size(), n = matrix[0].size();
vector height(n, 0), left(n, 0), right(n, n);
for (int i = 0; i < m; ++i) {
int cur_left = 0, cur_right = n;
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == '1') {
++height[j];
left[j] = max(left[j], cur_left);
} else {
height[j] = 0;
left[j] = 0;
cur_left = j + 1;
}
}
for (int j = n - 1; j >= 0; --j) {
if (matrix[i][j] == '1') {
right[j] = min(right[j], cur_right);
} else {
right[j] = n;
cur_right = j;
}
res = max(res, (right[j] - left[j]) * height[j]);
}
}
return res;
}
};```

```class Solution {
public:
int maximalRectangle(vector>& matrix) {
if (matrix.empty() || matrix[0].empty()) return 0;
int res = 0, m = matrix.size(), n = matrix[0].size();
vector> h_max(m, vector(n));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == '0') continue;
if (j > 0) h_max[i][j] = h_max[i][j - 1] + 1;
else h_max[i][0] = 1;
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (h_max[i][j] == 0) continue;
int mn = h_max[i][j];
res = max(res, mn);
for (int k = i - 1; k >= 0 && h_max[k][j] != 0; --k) {
mn = min(mn, h_max[k][j]);
res = max(res, mn * (i - k + 1));
}
}
}
return res;
}
};```