-
Notifications
You must be signed in to change notification settings - Fork 13
Expand file tree
/
Copy pathSolution0085.java
More file actions
125 lines (118 loc) · 4.8 KB
/
Copy pathSolution0085.java
File metadata and controls
125 lines (118 loc) · 4.8 KB
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
// 85. 最大矩形
/*
暴力破解/动态规划：
1、思路：遍历每个点，求以这个点为矩形右下角的所有矩形面积，比较并记录最大面积
2、二维数组width用于记录每行上每个点结尾的连续 1 的个数，即每行上每个点结尾时的宽度。width可以理解为dp数组，保存状态
3、从左到右遍历，计算并记录每行上每个点结尾时的宽度
4、计算面积
1）首先求出高度是 1 的矩形面积，即高度只有一行，宽度是该点记录的宽度
2）然后向上扩展一行，高度增加1，选出width当前列最小的数字，即多行的宽度选择最小的宽度为有效宽度，作为矩形的宽度，求出面积
3）然后继续向上扩展，重复步骤 2，求出所有可能的高度时的面积
*/
class Solution {
public int maximalRectangle(char[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int maxArea = 0;
int[][] width = new int[m][n];
for (int row = 0; row < m; row++) {
for (int col = 0; col < n; col++) {
if (matrix[row][col] == '1') {
width[row][col] = col == 0 ? 1 : width[row][col - 1] + 1;
}
int midWidth = width[row][col];
for (int rowUp = row; rowUp >= 0; rowUp--) {
int height = row - rowUp + 1;
midWidth = Math.min(midWidth, width[rowUp][col]);
maxArea = Math.max(maxArea, midWidth * height);
}
}
}
return maxArea;
}
}
/*
暴力破解：
1、遍历每一行的时候，从上往下计算每一列连续1的个数作为矩形高度，得到高度矩阵
2、遍历高度矩阵，以当前点的值作为矩形高度，向左右两边扩展高度大于等于当前高度的边界得到宽度，从而计算该点的最大面积
3、比较并记录矩阵所有点的最大面积，得出整个矩阵的最大面积
*/
class Solution {
public int maximalRectangle(char[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int[][] heights = new int[m][n];
int maxArea = 0;
for (int col = 0; col < n; col++) {
heights[0][col] = matrix[0][col] == '1' ? 1 : 0;
}
for (int row = 1; row < m; row++) {
for (int col = 0; col < n; col++) {
if (matrix[row][col] == '1') {
heights[row][col] = heights[row - 1][col] + 1;
}
}
}
for (int row = 0; row < m; row++) {
for (int col = 0; col < n; col++) {
if (heights[row][col] == 0 || heights[row][col] * n <= maxArea) {
continue;
}
int width = 1;
for (int k = col - 1; k >= 0; k--) {
if (heights[row][k] < heights[row][col]) {
break;
}
width++;
}
for (int k = col + 1; k < n; k++) {
if (heights[row][k] < heights[row][col]) {
break;
}
width++;
}
maxArea = Math.max(maxArea, width * heights[row][col]);
}
}
return maxArea;
}
}
/*
单调递增栈：
1、遍历每一行的时候，从上往下计算每一列连续1的个数作为矩形高度，得到高度数组
2、直接利用“84. 柱状图中最大的矩形”的解法，传入高度数组，得到最大矩形面积
3、在所有行的矩形面积结果中，记录最大面积
*/
class Solution {
public int maximalRectangle(char[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int[] heights = new int[n];
int maxArea = 0;
for (int row = 0; row < m; row++) {
for (int col = 0; col < n; col++) {
if (matrix[row][col] == '1') {
heights[col] += 1;
} else {
heights[col] = 0;
}
}
maxArea = Math.max(maxArea, largestRectangleArea(heights));
}
return maxArea;
}
private int largestRectangleArea(int[] heights) {
int res = 0;
int n = heights.length;
int[] newHeights = new int[n + 2];
System.arraycopy(heights, 0, newHeights, 1, n);
Deque<Integer> stack = new ArrayDeque<>();
for (int right = 0; right < n + 2; right++) {
while (!stack.isEmpty() && newHeights[right] < newHeights[stack.peek()]) {
int cur = stack.pop();
int left = stack.peek();
int area = (right - left - 1) * newHeights[cur];
res = Math.max(res, area);
}
stack.push(right);
}
return res;
}
}