FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
leetcode/problems/src/stack/MaximalRectangle.java at master · KindleBooks66/leetcode · GitHub
Uh oh!
There was an error while loading.
Please reload this page
.
KindleBooks66
/
leetcode
Public
forked from
gouthampradhan/leetcode
Notifications
You must be signed in to change notification settings
Fork
0
Star
0
Code
Pull requests
0
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
leetcode
/
problems
/
src
/
stack
/
MaximalRectangle.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
83 lines (78 loc) · 2.23 KB
Breadcrumbs
leetcode
/
problems
/
src
/
stack
/
MaximalRectangle.java
Copy path
File metadata and controls
83 lines (78 loc) · 2.23 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
package
stack
;
import
java
.
util
.
Stack
;
/**
* Created by gouthamvidyapradhan on 29/11/2017.
*
* <p>Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only
* 1's and return its area.
*
* <p>For example, given the following matrix:
*
* <p>1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 Return 6.
*
* <p>Solution O(n * m): This problem is similar to LargestRectangleInHistogram. Run the largest
* rectangle in histogram algorithm for each row.
*/
public
class
MaximalRectangle
{
/**
* Main method
*
* @param args
* @throws Exception
*/
public
static
void
main
(
String
[]
args
)
throws
Exception
{
char
[][]
matrix
= {
{
'1'
,
'0'
,
'1'
,
'0'
,
'0'
},
{
'1'
,
'0'
,
'1'
,
'1'
,
'1'
},
{
'1'
,
'1'
,
'1'
,
'1'
,
'1'
},
{
'1'
,
'0'
,
'0'
,
'1'
,
'0'
}
};
System
.
out
.
println
(
new
MaximalRectangle
().
maximalRectangle
(
matrix
));
}
public
int
maximalRectangle
(
char
[][]
matrix
) {
if
(
matrix
.
length
==
0
||
matrix
[
0
].
length
==
0
)
return
0
;
int
[]
A
=
new
int
[
matrix
[
0
].
length
];
int
max
=
Integer
.
MIN_VALUE
;
for
(
int
i
=
0
;
i
<
matrix
.
length
;
i
++) {
for
(
int
j
=
0
;
j
<
matrix
[
0
].
length
;
j
++) {
if
(
matrix
[
i
][
j
] ==
'1'
) {
if
(
i
>
0
&&
matrix
[
i
-
1
][
j
] ==
'1'
) {
A
[
j
] =
A
[
j
] +
1
;
}
else
{
A
[
j
] =
1
;
}
}
else
{
A
[
j
] =
0
;
}
}
// calculate max rectangle for this row
max
=
Math
.
max
(
max
,
getMaxRectangle
(
A
));
}
return
max
;
}
/**
* Get max rectangle algorithm similar to max rectangle in histogram
*
* @param heights
* @return
*/
private
int
getMaxRectangle
(
int
[]
heights
) {
int
maxArea
=
Integer
.
MIN_VALUE
;
Stack
<
Integer
>
stack
=
new
Stack
<>();
int
i
=
0
;
for
(;
i
<
heights
.
length
;
i
++) {
while
(!
stack
.
isEmpty
() &&
heights
[
stack
.
peek
()] >=
heights
[
i
]) {
int
top
=
stack
.
pop
();
int
base
=
stack
.
isEmpty
() ?
i
:
i
-
stack
.
peek
() -
1
;
maxArea
=
Math
.
max
(
maxArea
,
base
*
heights
[
top
]);
}
stack
.
push
(
i
);
}
while
(!
stack
.
isEmpty
()) {
int
top
=
stack
.
pop
();
int
base
=
stack
.
isEmpty
() ?
i
:
i
-
stack
.
peek
() -
1
;
maxArea
=
Math
.
max
(
maxArea
,
base
*
heights
[
top
]);
}
return
maxArea
;
}
}
Back
|
FazBrowse Home
|
New Git URL