# 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<vector<char> > &matrix) {
int res = 0;
vector<int> 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<int>& height) {
int res = 0;
stack<int> 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<vector<char>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return 0;
int res = 0, m = matrix.size(), n = matrix[0].size();
vector<int> height(n + 1);
for (int i = 0; i < m; ++i) {
stack<int> 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<vector<char>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return 0;
int res = 0, m = matrix.size(), n = matrix[0].size();
vector<int> 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<vector<char>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return 0;
int res = 0, m = matrix.size(), n = matrix[0].size();
vector<vector<int>> h_max(m, vector<int>(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;
}
};
``````

Maximal Square

Largest Rectangle in Histogram

https://leetcode.com/problems/maximal-rectangle/

https://leetcode.com/problems/maximal-rectangle/discuss/29054/Share-my-DP-solution

https://leetcode.com/problems/maximal-rectangle/discuss/29172/My-O(n3)-solution-for-your-reference

https://leetcode.com/problems/maximal-rectangle/discuss/225690/Java-solution-with-explanations-in-Chinese

https://leetcode.com/problems/maximal-rectangle/discuss/29064/A-O(n2)-solution-based-on-Largest-Rectangle-in-Histogram

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation