forked from yuanx/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMaximalRectangle.java
More file actions
74 lines (61 loc) · 1.7 KB
/
MaximalRectangle.java
File metadata and controls
74 lines (61 loc) · 1.7 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
// Form an array with each row, calculate the largest rectangle by using largestRectangleArea function, update the max
// could not pass the larger test all the time
import java.util.Stack;
public class Solution {
public int maximalRectangle(char[][] matrix) {
// Start typing your Java solution below
// DO NOT write main() function
int len = matrix.length;
if(len==0) return 0;
int len0 = matrix[0].length;
int maxarea = 0;
int[] arr = new int[len0];
for(int i=0; i<len; i++){
for(int j=0; j<len0; j++){
if(matrix[i][j]=='0')
arr[j]=0;
else
arr[j]+=1;
}
maxarea = Math.max(maxarea, largestRectangleArea(arr));
}
return maxarea;
}
public int largestRectangleArea(int[] height) {
// Start typing your Java solution below
// DO NOT write main() function
if(height.length == 0) return 0;
if(height.length == 1) return height[0];
Stack<Integer> hs = new Stack<Integer>();
Stack<Integer> inds = new Stack<Integer>();
hs.push(height[0]);
inds.push(0);
int localmax = 0;
int max = 0;
int lastindex = 0;
int lasth = 0;
for(int i=1; i<height.length; i++){
if(height[i]>hs.peek()){
hs.push(height[i]);
inds.push(i);
}
else if(height[i]<hs.peek()){
while(!hs.isEmpty() && hs.peek()>height[i]){
lasth = hs.pop();
lastindex = inds.pop();
localmax = (i-lastindex)*lasth;
max = max > localmax ? max : localmax;
}
hs.push(height[i]);
inds.push(lastindex);
}
}
while(!hs.isEmpty()){
lastindex = inds.pop();
lasth = hs.pop();
localmax = (height.length-lastindex)*lasth;
max = max > localmax ? max :localmax;
}
return max;
}
}