leetcode 85 Maximal Rectangle
Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.
Example:
1 | Input: |
用一个数组a[n]在存储每一行的累积的连续的1有多少
1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 对应的a为
1 0 1 0 0 2 0 2 1 1 3 1 3 2 2 4 0 0 3 0 那对于每一个a[n]，需要求他能组成的最大的长方形是多少。
用一个stack保存index，同时保证stack中所指向的a[index]是升序的。
- 每次遇到一个a[i]，都和stack中的a[peek]进行比较，如果大于a[peek]，继续入栈。
- 如果小于a[peek]，那么将peek pop出来
- 接下来计算包含peek在内，对大能组成的长方形是多大。
- 此时a[i]是peek右边第一个比peek小的数
- stack.peek是a[i]左边第一个比peek大的数(当stack为空的时候，left设置为-1)
- 这样一来，就可以求出来包含peek在内的最大的长方形的大小。
- 计算完peek之后，继续i保持不变，继续计算包括stack.peek在内能组成的最大的长方形。
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
36class Solution {
public int maximalRectangle(char[][] matrix) {
if (matrix.length == 0 || matrix[0].length == 0) {
return 0;
}
int max = Integer.MIN_VALUE;
int[] a = new int[matrix[0].length];
for (int i=0; i<matrix.length; i++) {
for (int j=0; j<matrix[0].length; j++) {
if (matrix[i][j] == '0')
a[j] = 0;
else {
a[j] += 1;
}
}
Stack<Integer> s = new Stack<>();
for(int j=0; j<=matrix[0].length; j++) {
int h = j == matrix[0].length?0: a[j];
if (s.isEmpty() || a[s.peek()] < h) {
s.push(j);
}
else {
int top = s.pop();
int left = -1;
if (!s.isEmpty())
left = s.peek();
int right = j;
max = Math.max(max, a[top]*(right-left-1));
j--;
}
}
}
return max;
}
}