Leetcode
Dynamic Programming
85 Maximal Rectangle

1. Question

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
For example, given the following matrix:
1
1 0 1 0 0
2
1 0 1 1 1
3
1 1 1 1 1
4
1 0 0 1 0
Copied!
Return 6.

2. Implementation

思路:这题和Largest Rectangle Histogram的做法完全一样,唯一的不同是,那题的输入就是代表不同高度的数组,而这题需要我们根据matrix每行每个列上连续的1的个数,计算出相应的高度。
1
class Solution {
2
public int maximalRectangle(char[][] matrix) {
3
if (matrix == null || matrix.length == 0) {
4
return 0;
5
}
6
7
Stack<Integer> stack = null;
8
int area = 0, maxArea = 0;
9
int m = matrix.length, n = matrix[0].length;
10
11
int[] heights = new int[n + 1];
12
13
for (int i = 0; i < m; i++) {
14
stack = new Stack<>();
15
16
for (int j = 0; j < n; j++) {
17
if (matrix[i][j] == '1') {
18
heights[j] += 1;
19
}
20
else {
21
heights[j] = 0;
22
}
23
}
24
25
for (int j = 0; j <= n; j++) {
26
int curHeight = j == n ? -1 : heights[j];
27
28
while (!stack.isEmpty() && heights[stack.peek()] > curHeight) {
29
int topIndex = stack.pop();
30
area = heights[topIndex] * (stack.isEmpty() ? j : j - stack.peek() - 1);
31
maxArea = Math.max(maxArea, area);
32
}
33
stack.push(j);
34
}
35
}
36
return maxArea;
37
}
38
}
Copied!

3. Time & Space Complexity

时间复杂度是O(mn), 空间复杂度O(n)