Difficulty:: Hard
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:
1
2
3
4
5
6
7
8
| Input:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
Output: 6
|
Solution
Language: Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| class Solution {
public int maximalRectangle(char[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return 0;
}
int max = 0;
int m = matrix.length;
int n = matrix[0].length;
int[][] dpLeft = new int[m][n];
int[][] dpUp = new int[m][n];
if (matrix[0][0] == '1') {
dpLeft[0][0] = 1;
dpUp[0][0] = 1;
max = 1;
}
for (int i = 1; i < n; i++) {
if (matrix[0][i] == '1') {
dpLeft[0][i] = dpLeft[0][i - 1] + 1;
dpUp[0][i] = 1;
max = Math.max(dpLeft[0][i], max);
}
}
for (int i = 1; i < m; i++) {
if (matrix[i][0] == '1') {
dpLeft[i][0] = 1;
dpUp[i][0] = dpUp[i - 1][0] + 1;
max = Math.max(dpUp[i][0], max);
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][j] != '1') {
continue;
}
dpLeft[i][j] = dpLeft[i][j - 1] + 1;
dpUp[i][j] = dpUp[i - 1][j] + 1;
int len = dpLeft[i][j];
int minHeight = dpUp[i][j];
for (int k = 0; k < len; k++) {
minHeight = Math.min(minHeight, dpUp[i][j - k]);
max = Math.max(minHeight * (k + 1), max);
}
}
}
return max;
}
}
|
单调栈解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| class Solution {
public int maximalRectangle(char[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return 0;
}
int max = 0;
int m = matrix.length;
int n = matrix[0].length;
int[] heights = new int[n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == '1') {
heights[j] += 1;
} else {
heights[j] = 0;
}
}
max = Math.max(maxRectangle(heights), max);
}
return max;
}
private int maxRectangle(int[] heights) {
Deque<Integer> stack = new ArrayDeque<>();
int max = 0;
stack.push(-1);
for (int i = 0; i < heights.length; i++) {
while (stack.peek() != -1 && heights[i] < heights[stack.peek()]) {
max = Math.max(max, heights[stack.pop()] * (i - stack.peek() - 1));
}
stack.push(i);
}
while (stack.peek() != -1) {
max = Math.max(max, heights[stack.pop()] * (heights.length - stack.peek() - 1));
}
return max;
}
}
|