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
- Method 1: Use the method of Monostack as question 84: 84. Largest Rectangle in Histogram
- we use a height array to save the historgram.
- if current value is 1, we increase the value saved in that index.
- if current value is 0, we set the value to 0.
class Solution {
public int maximalRectangle(char[][] matrix) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
int res = 0;
int[] height = new int[matrix[0].length + 1];
for(int row = 0; row < matrix.length; row++){
for(int i = 0; i < matrix[0].length; i++){
if(matrix[row][i] == '1') height[i]++;
else height[i] = 0;
}
Stack<Integer> stack = new Stack<>();
for(int j = 0; j <= matrix[0].length; j++){
while(!stack.isEmpty() && height[j] < height[stack.peek()]){
int h = height[stack.pop()];
int index = stack.isEmpty() ? -1: stack.peek();
res = Math.max(res, h * (j - index - 1));
}
stack.push(j);
}
}
return res;
}
}- Method 2: dp
- we define 3 arrays for each row:
- left(save the first index of 1 in current row, still need to compare with previous value), initial value is 0.
- right(save the last index of 1 in current row, need to compare with previous value), initialized with len.
- height(record the height as historgram)
- area = height * (right - left)
- we define 3 arrays for each row:
/**
Example:
0 1 2 3 4
row0 ["1","0","1","0","0"],
row1 ["1","0","1","1","1"],
row2 ["1","1","1","1","1"],
row3 ["1","0","0","1","0"]
height[]: height array saves the historgram for current row.
row0 [1,0,1,0,0],
row1 [2,0,2,1,1],
row2 [3,1,3,2,2],
row3 [4,0,0,3,0]
left[]: left array saves the first index in current row and we need to compare it with the previous row left array.
row0 [0,0,2,0,0],
row1 [0,0,2,2,2],
row2 [0,0,2,2,2],
row3 [0,0,0,3,0]
right[]: right array saves the last index in current row(need to compare it with the previous row right array.)
row0 [1,5,3,5,5],
row1 [1,5,3,5,5],
row2 [1,5,3,5,5],
row3 [1,5,5,4,5]
*/
class Solution {
public int maximalRectangle(char[][] matrix) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
int res = 0, len = matrix[0].length;
int[] left = new int[len];
int[] right = new int[len];
int[] height = new int[len];
for(int i = 0; i < len; i++) right[i] = len;
for(int row = 0; row < matrix.length; row++){
int cur_left = 0, cur_right = len;
for(int i = 0; i < len; i++){
if(matrix[row][i] == '0') height[i] = 0;
else height[i]++;
}
for(int i = 0; i < len; i++){
if(matrix[row][i] == '1'){
left[i] = Math.max(left[i], cur_left);
}else{
cur_left = i + 1;
left[i] = 0;
}
}
for(int i = len - 1; i >= 0; i--){
if(matrix[row][i] == '1'){
right[i] = Math.min(right[i], cur_right);
}else{
cur_right = i;
right[i] = len;
}
}
for(int i = 0; i < len; i++){
res = Math.max(res, height[i] * (right[i] - left[i]));
}
}
return res;
}
}-
Method 1: Stack
class Solution { public int maximalRectangle(char[][] matrix) { if(matrix.length == 0 || matrix[0].length == 0) return 0; int height = matrix.length, width = matrix[0].length; int[] dp = new int[width]; int res = 0; for(int i = 0; i < height; i++){ for(int j = 0; j < width; j++){ if(matrix[i][j] == '1') dp[j]++; else dp[j] = 0; } Stack<Integer> stack = new Stack<>(); for(int c = 0; c <= width; c++){ int hh = c == width ? 0: dp[c]; while(!stack.isEmpty() && hh < dp[stack.peek()]){ int h = dp[stack.pop()]; int index = stack.isEmpty() ? -1: stack.peek(); int area = h * (c - index - 1); res = Math.max(res, area); } stack.push(c); } } return res; } }
-
Method 2: dp
class Solution { public int maximalRectangle(char[][] matrix) { if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0; int h = matrix.length, width = matrix[0].length; int[] height = new int[width]; int[] left = new int[width]; int[] right = new int[width]; Arrays.fill(right, width); int res = 0; for(int i = 0; i < h; i++){ int curLeft = 0, curRight = width; for(int j = 0; j < width; j++){ // Calculate the height array if(matrix[i][j] == '1') height[j]++; else height[j] = 0; } for(int j = 0; j < width; j++){ if(matrix[i][j] == '1') left[j] = Math.max(curLeft, left[j]); else{ left[j] = 0; curLeft = j + 1; } } for(int j = width - 1; j >= 0; j--){ if(matrix[i][j] == '1') right[j] = Math.min(curRight, right[j]); else{ right[j] = width; curRight = j; } } for(int j = 0; j < width; j++){ res = Math.max(res, height[j] * (right[j] - left[j])); } } return res; } }