-
Notifications
You must be signed in to change notification settings - Fork 17
Expand file tree
/
Copy pathSolution.java
More file actions
101 lines (94 loc) · 3.06 KB
/
Solution.java
File metadata and controls
101 lines (94 loc) · 3.06 KB
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
package MaximalRectangle;
/**
* User: Danyang
* Date: 1/26/2015
* Time: 15:33
*
* Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
*/
public class Solution {
/**
* Brute force O(n^2)*O(n^2)
* Beyond brute force: O(n^2)*O(2n)
*
* v[i][j] vertical # continuous 1, upside
* h[i][j] horizontal # continuous 1, left-side
*
* Notice:
* 1. i, j, l, k
* @param matrix
* @return
*/
public int maximalRectangle(char[][] matrix) {
int m = matrix.length;
if(m==0)
return 0;
int n = matrix[0].length;
if(n==0)
return 0;
int[][] vertical = new int[m+1][n+1];
int[][] horizontal = new int[m+1][n+1];
for(int i=1; i<m+1; i++)
for(int j=1; j<n+1; j++) {
if(matrix[i-1][j-1]=='0') {
vertical[i][j] = 0;
horizontal[i][j] = 0;
}
else {
vertical[i][j] = vertical[i-1][j]+1;
horizontal[i][j] = horizontal[i][j-1]+1;
}
}
int maxa = 0;
for(int i=0; i<m; i++)
for(int j=0; j<n; j++) {
int height = Integer.MAX_VALUE;
for(int l=j; l>j-horizontal[i+1][j+1]; l--) {
height = Math.min(height, vertical[i+1][l+1]);
maxa = Math.max(maxa, height*(j-l+1));
}
}
return maxa;
}
public int maximalRectangle_error(char[][] matrix) {
int m = matrix.length;
if(m==0)
return 0;
int n = matrix[0].length;
if(n==0)
return 0;
int[][] vertical = new int[m+1][n+1];
int[][] horizontal = new int[m+1][n+1];
for(int i=1; i<m+1; i++)
for(int j=1; j<n+1; j++) {
if(matrix[i-1][j-1]=='0') {
vertical[i][j] = 0;
horizontal[i][j] = 0;
}
else {
vertical[i][j] = vertical[i-1][j]+1;
horizontal[i][j] = horizontal[i][j-1]+1;
}
}
int maxa = 0;
for(int i=0; i<m; i++)
for(int j=0; j<n; j++) {
int height = vertical[i+1][j+1];
int length = horizontal[i+1][j+1];
for(int l=j; l>j-horizontal[i+1][j+1]; l--)
height = Math.min(height, vertical[i+1][l+1]);
for(int k=i; k>i-vertical[i+1][j+1]; k--)
length = Math.min(length, horizontal[k+1][j+1]);
maxa = Math.max(maxa, Math.max(horizontal[i+1][j+1]*height, vertical[i+1][j+1]*length)); // logic flaw
}
return maxa;
}
public static void main(String[] args) {
int ret = new Solution().maximalRectangle(new char[][] {
{'1', '1', '0', '1'},
{'1', '1', '0', '1'},
{'1', '1', '1', '1'},
});
assert ret==6;
}
}