Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
Example 1:
Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] Output: 6 Explanation: The maximal rectangle is shown in the above picture.
Example 2:
Input: matrix = [["0"]] Output: 0
Example 3:
Input: matrix = [["1"]] Output: 1
Constraints:
rows == matrix.lengthcols == matrix[i].length1 <= row, cols <= 200matrix[i][j]is'0'or'1'.
Companies:
Google, Amazon, Apple, Dunzo, Bloomberg
Related Topics:
Array, Dynamic Programming, Stack, Matrix, Monotonic Stack
Similar Questions:
For each row:
- Calculate an
harray whereh[j]is the height of1s fromA[i][j]upwards. - Calculate
nextSmallerandprevSmallerusing Monotonic Stack wherenextSmaller/prevSmalleris the index of the next/previous smaller element inharray. (Refer to 496. Next Greater Element I (Easy)) - The answer is the maximum of
(nextSmaller - prevSmaller - 1) * h[j].
// OJ: https://leetcode.com/problems/maximal-rectangle/
// Author: github.com/lzl124631x
// Time: O(MN)
// Space: O(N)
class Solution {
public:
int maximalRectangle(vector<vector<char>>& A) {
int M = A.size(), N = A[0].size(), ans = 0;
vector<int> h(N), nextSmaller(N);
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
h[j] = A[i][j] == '0' ? 0 : (h[j] + 1);
}
stack<int> s;
for (int j = N - 1; j >= 0; --j) {
while (s.size() && h[j] <= h[s.top()]) s.pop();
nextSmaller[j] = s.size() ? s.top() : N;
s.push(j);
}
s = {};
for (int j = 0; j < N; ++j) {
while (s.size() && h[j] <= h[s.top()]) s.pop();
int prevSmaller = s.size() ? s.top() : -1;
ans = max(ans, (nextSmaller[j] - prevSmaller - 1) * h[j]);
s.push(j);
}
}
return ans;
}
};We can reuse the solution for 84. Largest Rectangle in Histogram (Hard).
// OJ: https://leetcode.com/problems/maximal-rectangle/
// Author: github.com/lzl124631x
// Time: O(MN)
// Space: O(N)
class Solution {
public:
int maximalRectangle(vector<vector<char>>& A) {
int M = A.size(), N = A[0].size(), ans = 0;
vector<int> h(N + 1);
for (int i = 0; i < M; ++i) {
stack<int> s;
for (int j = 0; j <= N; ++j) {
h[j] = j < N && A[i][j] == '1' ? (h[j] + 1) : 0;
while (s.size() && h[j] <= h[s.top()]) {
int height = h[s.top()];
s.pop();
int left = s.size() ? s.top() : -1;
ans = max(ans, (j - left - 1) * height);
}
s.push(j);
}
}
return ans;
}
};// OJ: https://leetcode.com/problems/maximal-rectangle/
// Author: github.com/lzl124631x
// Time: O(MN)
// Space: O(N)
class Solution {
public:
int maximalRectangle(vector<vector<char>>& A) {
int M = A.size(), N = A[0].size(), ans = 0;
vector<int> h(N), prevSmaller(N, -1), nextSmaller(N, N);
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) h[j] = A[i][j] == '1' ? h[j] + 1 : 0;
for (int j = N - 2; j >= 0; --j) {
int k = j + 1;
while (k < N && h[k] >= h[j]) k = nextSmaller[k];
nextSmaller[j] = k;
}
for (int j = 1; j < N; ++j) {
int k = j - 1;
while (k >= 0 && h[k] >= h[j]) k = prevSmaller[k];
prevSmaller[j] = k;
}
for (int j = 0; j < N; ++j) ans = max(ans, (nextSmaller[j] - prevSmaller[j] - 1) * h[j]);
}
return ans;
}
};Let height[i][j] be the height of the bar from A[i][j] to A[0][j].
Let left[i][j] be the index of the leftmost column such that the bar at A[i][k] has height at least height[i][j] for all left[i][j] <= k <= j.
Let right[i][j] be the index of the rightmost column such that the bar at A[i][k] has height at least height[i][j] for all j <= k < right[i][j].
So the answer is the max (right[i][j] - left[i][j]) * height[i][j].
We can use the following equations to get the values.
height[i][j] = A[i][j] == '1' ? height[i - 1][j] + 1 : 0
left[i][j] = max(left[i - 1][j], curLeft) // If A[i][j] == '1'
= 0 // If A[i][j] == '0'
where curLeft is the index of the leftmost column such that A[i][k] are all ones for `curLeft <= k <= j`
right[i][j] = min(right[i - 1][j], curRight) // If A[i][j] == '1'
= N // If A[i][j] == '0'
where curRight is the index of the rightmost column such that A[i][k] are all ones for all `j <= k < curRight`
Since height[i][j], left[i][j] and right[i][j] are only dependent on the value at the same column in the previous row, we can simply use 1D arrays to store those values.
// OJ: https://leetcode.com/problems/maximal-rectangle/
// Author: github.com/lzl124631x
// Time: O(MN)
// Space: O(N)
class Solution {
public:
int maximalRectangle(vector<vector<char>>& A) {
if (A.empty() || A[0].empty()) return 0;
int ans = 0, M = A.size(), N = A[0].size();
vector<int> left(N, 0), right(N, N), height(N, 0);
for (int i = 0; i < M; ++i) {
int curLeft = 0, curRight = N;
for (int j = 0; j < N; ++j) height[j] = A[i][j] == '1' ? height[j] + 1 : 0;
for (int j = 0; j < N; ++j) {
if (A[i][j] == '1') left[j] = max(left[j], curLeft);
else {
left[j] = 0;
curLeft = j + 1;
}
}
for (int j = N - 1; j >= 0; --j) {
if (A[i][j] == '1') right[j] = min(right[j], curRight);
else {
right[j] = N;
curRight = j;
}
}
for (int j = 0; j < N; ++j) ans = max(ans, (right[j] - left[j]) * height[j]);
}
return ans;
}
};