GuilinDev
Lc0085
05 August 2008
85 - Maximum 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
2
3
4
5
6
7
8
Input:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
Output: 6
题意和分析
1) 84 题栈的解法，注意观察橙色部分，就是从上到下按照层数遍历，对每一行建立类似84题的柱状图，然后求出最大矩形的面积。
2) DP解法，参考这里(https://leetcode.com/problems/maximal-rectangle/discuss/29054/Share-my-DP-solution)
The DP solution proceeds row by row, starting from the first row. Let the maximal rectangle area at row i and column j be computed by [right(i,j) - left(i,j)]*height(i,j).
All the 3 variables left, right, and height can be determined by the information from previous row, and also information from the current row. So it can be regarded as a DP solution. The transition equations are:
left(i,j) = max(left(i-1,j), cur_left), cur_left can be determined from the current row
right(i,j) = min(right(i-1,j), cur_right), cur_right can be determined from the current row
height(i,j) = height(i-1,j) + 1, if matrix[i][j]==’1’;
height(i,j) = 0, if matrix[i][j]==’0’
比较难理解，需要结合84题和上面的解法来看，上面的解法我们更新一次 heights，就利用84题的算法来找一次当前柱子左右两边的非递增柱子，并更新最大面积，但实际上，通过寻找左右两边的最近的非递增柱子的这个过程，可以通过上一次的左右两边非递增的柱子的结果来找。
定义一下leftLessMin [ ] 和 rightLessMin [ ] 的含义， leftLessMin [ i ] 代表左边第一个比当前柱子矮的下标，如下图橙色柱子时当前遍历的柱子。rightLessMin [ ] 是右边第一个比当前矮的柱子下标。
下面以寻找左边刚好比当前小的柱子为例，如果当前新增的层全部是 1，则leftLessMin [ ]无需改变
如果当前新增的层含有0，如下图
考虑最后一个柱子的更新。上一层的 leftLessMin = 1，也就是蓝色 0 的位置是第一个比它低的柱子。但是在当前层，由于中间出现了 0。所以不再是上一轮的 leftLessMin ，而是和上次出现 0 的位置进行比较（因为 0 一定比当前柱子小），谁的下标大，更接近当前柱子，就选择谁。上图中出现 0 的位置是 2，之前的 leftLessMin 是 1，选一个较大的，那就是 2 了。
代码
用栈求最大矩形面积的做法，时间复杂度：O(mn)，空间复杂度：O(n)。
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
class Solution {
public int maximalRectangle(char[][] matrix) {
if (matrix.length == 0) {
return 0;
}
int[] heights = new int[matrix[0].length];
int maxArea = 0;
for (int row = 0; row < matrix.length; row++) {
//遍历某行中的每一列，当前行从左到右构建高度数组作为参数
for (int col = 0; col < matrix[0].length; col++) {
if (matrix[row][col] == '1') {
heights[col] += 1;
} else {
heights[col] = 0;
}
}
//调用84题的解法，更新函数
maxArea = Math.max(maxArea, largestRectangleArea(heights));
}
return maxArea;
}
// 84题的解法直接拷过来
public int largestRectangleArea(int[] heights) {
if (heights == null || heights.length == 0) {
return 0;
}
int len = heights.length;
Stack<Integer> stack = new Stack<>();
int result = 0;
for (int i = 0; i <= len; i++) { // 末尾会多一个哨兵节点
int height = (i == len) ? 0 : heights[i];
if (stack.isEmpty() || height >= heights[stack.peek()]) { // 单调递增，入栈
stack.push(i);
} else { // 当前柱子比前面的柱子矮了
int preIndex = stack.pop();
int currArea = 0;
if (stack.isEmpty()) { // pop出哨兵节点了，计算最矮的柱子乘以所有柱子数目的面积
currArea = heights[preIndex] * i;
} else { // 正常计算
currArea = heights[preIndex] * (i - 1 - stack.peek());
}
result = Math.max(result, currArea);
i--; // 继续退回前面高的柱子，计算面积
}
}
return result;
}
}
DP，时间复杂度：O(mn)，空间复杂度：O(n)。
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
class Solution {
public int maximalRectangle(char[][] matrix) {
if (matrix.length == 0) {
return 0;
}
int maxArea = 0;
int cols = matrix[0].length;
int[] leftLessMin = new int[cols];
int[] rightLessMin = new int[cols];
Arrays.fill(leftLessMin, -1); //初始化为 -1，也就是最左边
Arrays.fill(rightLessMin, cols); //初始化为 cols，也就是最右边
int[] heights = new int[cols];
for (int row = 0; row < matrix.length; row++) {
//更新所有高度
for (int col = 0; col < cols; col++) {
if (matrix[row][col] == '1') {
heights[col] += 1;
} else {
heights[col] = 0;
}
}
//更新所有leftLessMin
int boundary = -1; //记录上次出现 0 的位置
for (int col = 0; col < cols; col++) {
if (matrix[row][col] == '1') {
//和上次出现 0 的位置比较
leftLessMin[col] = Math.max(leftLessMin[col], boundary);
} else {
//当前是 0 代表当前高度是 0，所以初始化为 -1，防止对下次循环的影响
leftLessMin[col] = -1;
//更新 0 的位置
boundary = col;
}
}
//右边同理
boundary = cols;
for (int col = cols - 1; col >= 0; col--) {
if (matrix[row][col] == '1') {
rightLessMin[col] = Math.min(rightLessMin[col], boundary);
} else {
rightLessMin[col] = cols;
boundary = col;
}
}
//更新所有面积
for (int col = cols - 1; col >= 0; col--) {
int area = (rightLessMin[col] - leftLessMin[col] - 1) * heights[col];
maxArea = Math.max(area, maxArea);
}
}
return maxArea;
}
}