友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
85. 最大矩形
给定一个仅包含 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"]] 输出：0
示例 3：
输入：matrix = [["1"]] 输出：1
提示：
-
rows == matrix.length -
cols == matrix[0].length -
1 <= row, cols <= 200 -
matrix[i][j]为0或1
思路分析
还想暴力解决，奈何一团浆糊！
计算每一行的高度，利用这个高度，使用与 84. 柱状图中最大的矩形 中单调栈的思路来解决这个问题！
-
一刷
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-06-25 20:59:45
*/
public int maximalRectangle(char[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return 0;
}
int[] heights = new int[matrix[0].length];
int result = 0;
for (int row = 0; row < matrix.length; row++) {
// 计算出每一行的高度
for (int column = 0; column < matrix[row].length; column++) {
if (matrix[row][column] == '1') {
heights[column] += 1;
} else {
heights[column] = 0;
}
}
// 利用每一行的高度，去计算可以组成的最大矩阵面积
result = Math.max(result, largestRectangleArea(heights));
}
return result;
}
private int largestRectangleArea(int[] heights) {
int length = heights.length;
if (length == 1) {
return heights[0];
}
int[] newHeights = new int[length + 2];
// 两端两个哨兵
newHeights[0] = 0;
newHeights[length + 1] = 0;
System.arraycopy(heights, 0, newHeights, 1, length);
heights = newHeights;
Deque<Integer> stack = new ArrayDeque<>();
stack.push(heights[0]);
int result = 0;
for (int i = 1; i < newHeights.length; i++) {
while (heights[i] < heights[stack.peek()]) {
Integer left = stack.pop();
// 以弹出的栈顶元素为高，因为有可能一柱擎天就是最大的面积
// 另外，弹出一个元素后，如果当前高度还是比栈顶元素低，
// 那么下次再弹出时，就会一个更低的高度去计算从栈顶元素到 i-1 的矩阵了
int hight = heights[left];
// 因为 heights[i] 已经变低了，所以，得从 i-1 开始想前算
int width = (i - 1) - stack.peek();
result = Math.max(result, hight * width);
}
stack.push(i);
}
return result;
}