剑指offer040-矩阵中的最大的矩形
题目
给定一个由 0 和 1 组成的矩阵 matrix ，找出只包含 1 的最大矩形，并返回其面积。
注意：此题 matrix 输入格式为一维 01 字符串数组。
示例 1：
输入：matrix = ["10100","10111","11111","10010"]
输出：6
解释：最大矩形如上图所示。
示例 2：
输入：matrix = []
输出：0
示例 3：
输入：matrix = ["0"]
输出：0
示例 4：
输入：matrix = ["1"]
输出：1
示例 5：
输入：matrix = ["00"]
输出：0
提示：
rows == matrix.lengthcols == matrix[0].length0 <= row, cols <= 200matrix[i][j] 为 '0' 或 '1'
注意：本题与主站 85 题相同（输入参数格式不同）： https://leetcode-cn.com/problems/maximal-rectangle/
Related Topics
栈数组动态规划矩阵单调栈思路
参考直方图的最大面积
需要计算每一块的最大面积
代码
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
| class Solution {
public int maximalRectangle(String[] matrix) {
if (matrix.length == 0) {
return 0;
}
int m = matrix.length;
int n = matrix[0].length();
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dp[i][j] = Integer.valueOf(String.valueOf(matrix[i].charAt(j)));
}
}
for (int i = 1; i < m; i++) {
for (int j = 0; j < n; j++) {
if(dp[i][j] != 0){
dp[i][j] = dp[i - 1][j] + dp[i][j];
}
}
}
int res = Integer.MIN_VALUE;
for (int i = 0; i < m; i++) {
int v = findMax(dp[i]);
res = Math.max(res, v);
}
return res;
}
int findMax(int[] arr) {
Stack<Integer> stack = new Stack<>();
stack.push(-1);
int res = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
while (stack.peek() != -1 && arr[i] < arr[stack.peek()]) {
int height = arr[stack.pop()];
int width = i - stack.peek() - 1;
res = Math.max(res, height * width);
}
stack.push(i);
}
while (stack.peek() != -1) {
int height = arr[stack.pop()];
int width = arr.length - stack.peek() - 1;
res = Math.max(res, height * width);
}
return res;
}
}
|