-
Notifications
You must be signed in to change notification settings - Fork 1
/
index.js
58 lines (53 loc) · 1.44 KB
/
index.js
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
/**
* @param {character[][]} matrix
* @return {number}
*/
var maximalRectangle = function(matrix) {
let m = matrix.length;
if(m === 0) return 0;
let n = matrix[0].length;
let max = 0;
let INF = 1000000;
for(var i = 0; i<m; i++){
for(var j = 0; j<n; j++){
if(matrix[i][j] === '1'){
max = Math.max(max, find(i, j));
}
}
}
function find(x, y){
let heights = [];
for(var i = x; i<m; i++){
let item = 0;
for(var j = y; j<n; j++){
if(matrix[i][j] === '1'){
item++;
}else if(j === y){
i = INF;
j = INF;
}else{
j = INF;
}
}
heights.push(item);
}
return largestRectangleArea(heights);
}
function largestRectangleArea(heights) {
let max = 0;
let INF = 10000000;
let stack = [];
heights.push(0);
for(var i = 0; i<heights.length; i++){
if(stack.length === 0 || heights[stack.slice(-1)[0]] < heights[i]){
stack.push(i);
}else{
let t = stack.pop();
max = Math.max(max, (stack.length === 0 ? i : (i-stack.slice(-1)[0] -1)) * heights[t]);
i--;
}
}
return max;
};
return max;
};