FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
LeetCode/src/main/java/L0085_MaximalRectangle.java at master · LjyYano/LeetCode · GitHub
LjyYano
/
LeetCode
Public
Notifications
You must be signed in to change notification settings
Fork
125
Star
342
Code
Issues
0
Pull requests
0
Actions
Projects
Wiki
Security and quality
0
Insights
Additional navigation options
Code
Issues
Pull requests
Actions
Projects
Wiki
Security and quality
Insights
Expand file tree
Breadcrumbs
LeetCode
/
src
/
main
/
java
/
L0085_MaximalRectangle.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
144 lines (130 loc) · 4.83 KB
Breadcrumbs
LeetCode
/
src
/
main
/
java
/
L0085_MaximalRectangle.java
Copy path
File metadata and controls
144 lines (130 loc) · 4.83 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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
/**
* https://leetcode.cn/problems/maximal-rectangle/
*
* 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
*
* 示例 1：
* 
* 输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
* 输出：6
* 解释：最大矩形如上图所示。
*
* 示例 2：
* 输入：matrix = []
* 输出：0
*
* 示例 3：
* 输入：matrix = [["0"]]
* 输出：0
*
* 示例 4：
* 输入：matrix = [["1"]]
* 输出：1
*
* 示例 5：
* 输入：matrix = [["0","0"]]
* 输出：0
*
* 提示：
* - rows == matrix.length
* - cols == matrix[0].length
* - 1 <= row, cols <= 200
* - matrix[i][j] 为 '0' 或 '1'
*/
public
class
L0085_MaximalRectangle
{
public
int
maximalRectangle
(
char
[][]
matrix
) {
if
(
matrix
==
null
||
matrix
.
length
==
0
||
matrix
[
0
].
length
==
0
) {
return
0
;
}
int
rows
=
matrix
.
length
;
int
cols
=
matrix
[
0
].
length
;
// 记录每个位置上方连续 1 的个数
int
[]
heights
=
new
int
[
cols
];
int
maxArea
=
0
;
// 逐行处理，将问题转化为柱状图中最大的矩形问题
for
(
int
i
=
0
;
i
<
rows
;
i
++) {
// 更新每列的高度
for
(
int
j
=
0
;
j
<
cols
;
j
++) {
if
(
matrix
[
i
][
j
] ==
'1'
) {
heights
[
j
]++;
}
else
{
heights
[
j
] =
0
;
}
}
// 计算当前行构成的柱状图中的最大矩形面积
maxArea
=
Math
.
max
(
maxArea
,
largestRectangleArea
(
heights
));
}
return
maxArea
;
}
// 复用第 84 题的解法，计算柱状图中最大的矩形面积
private
int
largestRectangleArea
(
int
[]
heights
) {
// 创建一个新数组，在首尾添加高度为 0 的柱子，方便处理边界情况
int
[]
newHeights
=
new
int
[
heights
.
length
+
2
];
System
.
arraycopy
(
heights
,
0
,
newHeights
,
1
,
heights
.
length
);
// 使用单调栈，栈中存储柱子的索引
int
[]
stack
=
new
int
[
newHeights
.
length
];
int
top
= -
1
;
int
maxArea
=
0
;
// 遍历每个柱子
for
(
int
i
=
0
;
i
<
newHeights
.
length
;
i
++) {
// 当栈不为空，且当前柱子高度小于栈顶柱子高度时
while
(
top
!= -
1
&&
newHeights
[
i
] <
newHeights
[
stack
[
top
]]) {
// 弹出栈顶元素，计算以该柱子为高度的最大矩形面积
int
height
=
newHeights
[
stack
[
top
--]];
// 宽度为当前位置到新的栈顶位置之间的距离
int
width
=
i
-
stack
[
top
] -
1
;
maxArea
=
Math
.
max
(
maxArea
,
height
*
width
);
}
// 将当前柱子的索引入栈
stack
[++
top
] =
i
;
}
return
maxArea
;
}
public
static
void
main
(
String
[]
args
) {
L0085_MaximalRectangle
solution
=
new
L0085_MaximalRectangle
();
// 测试用例 1
char
[][]
matrix1
= {
{
'1'
,
'0'
,
'1'
,
'0'
,
'0'
},
{
'1'
,
'0'
,
'1'
,
'1'
,
'1'
},
{
'1'
,
'1'
,
'1'
,
'1'
,
'1'
},
{
'1'
,
'0'
,
'0'
,
'1'
,
'0'
}
};
System
.
out
.
println
(
"测试用例 1:"
);
System
.
out
.
println
(
"输入: matrix ="
);
printMatrix
(
matrix1
);
System
.
out
.
println
(
"输出: "
+
solution
.
maximalRectangle
(
matrix1
));
System
.
out
.
println
();
// 测试用例 2：空矩阵
char
[][]
matrix2
= {};
System
.
out
.
println
(
"测试用例 2:"
);
System
.
out
.
println
(
"输入: matrix = []"
);
System
.
out
.
println
(
"输出: "
+
solution
.
maximalRectangle
(
matrix2
));
System
.
out
.
println
();
// 测试用例 3：单个 0
char
[][]
matrix3
= {{
'0'
}};
System
.
out
.
println
(
"测试用例 3:"
);
System
.
out
.
println
(
"输入: matrix = [[
\"
0
\"
]]"
);
System
.
out
.
println
(
"输出: "
+
solution
.
maximalRectangle
(
matrix3
));
System
.
out
.
println
();
// 测试用例 4：单个 1
char
[][]
matrix4
= {{
'1'
}};
System
.
out
.
println
(
"测试用例 4:"
);
System
.
out
.
println
(
"输入: matrix = [[
\"
1
\"
]]"
);
System
.
out
.
println
(
"输出: "
+
solution
.
maximalRectangle
(
matrix4
));
}
// 辅助方法：打印矩阵
private
static
void
printMatrix
(
char
[][]
matrix
) {
System
.
out
.
println
(
"["
);
for
(
char
[]
row
:
matrix
) {
System
.
out
.
print
(
" ["
);
for
(
int
j
=
0
;
j
<
row
.
length
;
j
++) {
System
.
out
.
print
(
"
\"
"
+
row
[
j
] +
"
\"
"
);
if
(
j
<
row
.
length
-
1
) {
System
.
out
.
print
(
","
);
}
}
System
.
out
.
println
(
"]"
);
}
System
.
out
.
println
(
"]"
);
}
}
Back
|
FazBrowse Home
|
New Git URL