forked from leetcoders/LeetCode-Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMaximalRectangle.java
More file actions
95 lines (93 loc) · 3.39 KB
/
MaximalRectangle.java
File metadata and controls
95 lines (93 loc) · 3.39 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
/*
Author: Andy, nkuwjg@gmail.com
Date: Jan 29, 2015
Problem: Maximal Rectangle
Difficulty: Medium
Source: https://oj.leetcode.com/problems/maximal-rectangle/
Notes:
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
Solution: 1. dp.
a) dp[i][j] records the number of consecutive '1' on the left and up of the element matrix[i][j].
b) For each element(i,j), calculate the area of rectangle including the element itself.
2. calculate 'Largest Rectangle in Histogram' for each row.
3. Time : O(n ^ 2), Space : O(n).
*/
public class Solution {
public int maximalRectangle_1(char[][] matrix) {
if (matrix.length == 0 || matrix[0].length == 0) return 0;
int M = matrix.length, N = matrix[0].length;
int[][][] dp = new int[M][N][2];
int res = 0;
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (matrix[i][j] == '0') continue;
dp[i][j][0] = (j==0)?1:dp[i][j-1][0] + 1;
dp[i][j][1] = (i==0)?1:dp[i-1][j][1] + 1;
int minheight = dp[i][j][1];
for (int k = j; k > j - dp[i][j][0]; --k) {
minheight = Math.min(minheight, dp[i][k][1]);
res = Math.max(res, minheight*(j-k+1));
}
}
}
return res;
}
public int cal(int[] dp) {
int N = dp.length;
Stack<Integer> stk = new Stack<Integer>();
int i = 0, res = 0;
while (i < N) {
if (stk.empty() || dp[i] >= dp[stk.peek()]) {
stk.push(i++);
continue;
}
int idx = stk.pop();
int width = stk.empty()?i:(i-stk.peek()-1);
res = Math.max(res, width*dp[idx]);
}
return res;
}
public int maximalRectangle_2(char[][] matrix) {
if (matrix.length == 0 || matrix[0].length == 0) return 0;
int M = matrix.length, N = matrix[0].length;
int[] dp = new int[N+1];
int res = 0;
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (matrix[i][j] == '0') dp[j] = 0;
else dp[j] = dp[j] + 1;
}
res = Math.max(res, cal(dp));
}
return res;
}
public int maximalRectangle(char[][] matrix) {
if (matrix.length == 0 || matrix[0].length == 0) return 0;
int M = matrix.length, N = matrix[0].length;
int[] L = new int[N]; Arrays.fill(L,0);
int[] R = new int[N]; Arrays.fill(R,N);
int[] H = new int[N]; Arrays.fill(H,0);
int res = 0;
for (int i = 0; i < M; ++i) {
int left = 0, right = N;
for (int j = 0; j < N; ++j) {
if (matrix[i][j] == '1') {
L[j] = Math.max(L[j], left);
H[j] = H[j] + 1;
} else {
H[j] = 0; L[j] = 0; R[j] = N;
left = j + 1;
}
}
for (int j = N - 1; j >= 0; --j) {
if (matrix[i][j] == '1') {
R[j] = Math.min(R[j], right);
res = Math.max(res, (R[j]-L[j])*H[j]);
} else {
right = j;
}
}
}
return res;
}
}