今日算法之_63_最大矩形
前言
Github:https://github.com/HealerJean
1、最大矩形
给定一个仅包含 0 和 1 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。
示例:
输入:
[
['1','0','1','0','0'],
['1','0','1','1','1'],
['1','1','1','1','1'],
['1','0','0','1','0']
]
输出: 6
1.1、解题思路
将上面的额数组变成整形数组。然后每一列的值,就类似于柱状土中的最大矩形面积
解题思路:
{'1', '0', '1', '0', '0'},
{'1', '0', '1', '1', '1'},
{'1', '1', '1', '1', '1'},
{'1', '0', '0', '1', '0'}
变成如下的,求矩形
{1, 0, 1, 0, 0},
{1, 0, 3, 2, 1},
{5, 4, 3, 2, 1},
{1, 0, 0, 1, 0}
1、先确定最后一列的值,然后依次确定每一行的值
for (int i = 0; i < m; i++) {
if (matrix[i][n-1] == '1'){
dp[i][n - 1] = 1 ;
}
}
for (int i = 0; i < m; i++) {
for (int j = n - 2; j >= 0; j--) {
if (matrix[i][j] == '1'){
dp[i][j] = 1 + dp[i][j + 1];
}
}
}
3、然后按照列进行推进,按照我们之前的柱状图求矩形最大面积
int res = 0;
//以列推进。计算柱状最大面积,将 行坐标i放到栈里面去
for(int j = 0; j < n; j++) {
Stack<Integer> stack = new Stack<>();
stack.push(-1);
for(int i = 0; i < m; i++) {
while (stack.peek() != -1 && dp[i][j] < dp[stack.peek()][j]) {
res = Math.max(res, dp[stack.pop()][j] * (i - stack.peek() -1));
}
stack.push(i);
}
while (stack.peek() != -1){
res = Math.max(res, dp[stack.pop()][j] * (m - stack.peek() -1));
}
}
1.2、算法
public int maximalRectangle(char[][] matrix) {
//边界条件
if(null == matrix || 0 == matrix.length) {
return 0;
}
int m = matrix.length;
int n = matrix[0].length;
int[][] dp = new int[m][n];
//从倒数第一列开始 dp[i][n-1]
for (int i = 0; i < m; i++) {
if (matrix[i][n-1] == '1'){
dp[i][n - 1] = 1 ;
}
}
//从倒数第二列开始继续往前推,数组默认就是0,所以只要求出1的就可以了
for (int i = 0; i < m; i++) {
for (int j = n - 2; j >= 0; j--) {
if (matrix[i][j] == '1'){
dp[i][j] = 1 + dp[i][j + 1];
}
}
}
int res = 0;
//以列推进。计算柱状最大面积,将 行坐标i放到栈里面去
for(int j = 0; j < n; j++) {
Stack<Integer> stack = new Stack<>();
stack.push(-1);
for(int i = 0; i < m; i++) {
while (stack.peek() != -1 && dp[i][j] < dp[stack.peek()][j]) {
res = Math.max(res, dp[stack.pop()][j] * (i - stack.peek() -1));
}
stack.push(i);
}
while (stack.peek() != -1){
res = Math.max(res, dp[stack.pop()][j] * (m - stack.peek() -1));
}
}
return res;
}
1.3、测试
@Test
public void test(){
char[][] matrix = {
{'1', '0', '1', '0', '0'},
{'1', '0', '1', '1', '1'},
{'1', '1', '1', '1', '1'},
{'1', '0', '0', '1', '0'}
};
System.out.println(maximalRectangle(matrix));
}