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.
Test Cases
Example 1:
| 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 |
Input: grid = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Solution
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int rows = matrix.size(), cols = matrix[0].size();
vector<int> histogram(cols, 0);
for(int i=0; i<cols; i++) {
histogram[i] = matrix[0][i] - '0';
}
int maxArea = largestHistogram(histogram);
for(int i=1; i<rows; i++) {
for(int j=0; j<cols; j++) {
histogram[j] = matrix[i][j] == '1' ? histogram[j] + 1 : 0;
}
maxArea = max(maxArea, largestHistogram(histogram));
}
return maxArea;
}
int largestHistogram(vector<int> &matrix) {
stack<int> st;
int n = matrix.size();
int maxArea = 0, i = 0;
while(i<n) {
if (st.empty() || matrix[st.top()] <= matrix[i]) {
st.push(i++);
} else {
int top = st.top(); st.pop();
int width = st.empty() ? i : i - st.top() - 1;
maxArea = max(maxArea, matrix[top]*width);
}
}
while(!st.empty()) {
int top = st.top(); st.pop();
int width = st.empty() ? n : n - st.top() - 1;
maxArea = max(maxArea, matrix[top]*width);
}
return maxArea;
}
};class Solution {
public int maximalRectangle(char[][] matrix) {
int rows = matrix.length, cols = matrix[0].length;
int[] histogram = new int[cols];
for(int i=0; i<cols; i++) {
histogram[i] = matrix[0][i] - '0';
}
int maxArea = largestRectangleArea(histogram);
for(int i=1; i<rows; i++) {
for(int j=0; j<cols; j++) {
histogram[j] = matrix[i][j] == '1' ? histogram[j]+1 : 0;
}
int result = largestRectangleArea(histogram);
maxArea = Math.max(maxArea, result);
}
return maxArea;
}
private int largestRectangleArea(int[] heights) {
Stack<Integer> stack = new Stack<>();
int n = heights.length;
int maxArea = 0;
int i=0;
while(i<n) {
if (stack.isEmpty() || heights[stack.peek()] <= heights[i]) {
stack.push(i++);
} else {
int top = stack.pop();
int width = stack.isEmpty() ? i : i - stack.peek() - 1;
maxArea = Math.max(maxArea, heights[top]*width);
}
}
while(!stack.isEmpty()) {
int top = stack.pop();
int width = stack.isEmpty() ? n : n - stack.peek() - 1;
maxArea = Math.max(maxArea, heights[top]*width);
}
return maxArea;
}
}