85. Maximal Rectangle
1. Description
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.
2. Example
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
3. Constraints
- rows == matrix.length
- cols == matrix[i].length
- 1 <= row, cols <= 200
- matrix[i][j] is ‘0’ or ‘1’.
4. Solutions
Monotonic Stackgit
m = matrix.size(), n = matrix.front().size()
Time complexity: O(mn)
Space complexity: O(mn)
class Solution {
public:
int maximalRectangle(const vector<vector<char>> &matrix) {
if (matrix.empty() || matrix.front().empty()) {
return 0;
}
vector<vector<int>> continuous_one_count(
matrix.size() + 1, vector<int>(matrix.front().size()));
for (int i = 0; i < matrix.size(); ++i) {
for (int j = 0; j < matrix.front().size(); ++j) {
continuous_one_count[i][j] =
matrix[i][j] == '0' ? 0 : (1 + (j == 0 ? 0 : continuous_one_count[i][j - 1]));
}
}
int max_rectangle = 0;
for (int j = 0; j < matrix.front().size(); ++j) {
stack<int> mono_increase;
for (int i = 0; i <= matrix.size(); ++i) {
while (!mono_increase.empty() &&
continuous_one_count[i][j] < continuous_one_count[mono_increase.top()][j]) {
int index = mono_increase.top();
mono_increase.pop();
int up = mono_increase.empty() ? -1 : mono_increase.top();
max_rectangle =
max(continuous_one_count[index][j] * (i - up - 1), max_rectangle);
}
mono_increase.push(i);
}
}
return max_rectangle;
}
};