问题描述:
对于了解84号算法题的同学先看一下这个图,我们再来解此题:
把它倒置过来,像不像84号算法题的解决问题分析的过程,所以我们只需要对84号应用了单调栈的模式去解决求最大矩阵,代码如下:
/*
解题关键,对二维二进制矩阵的抽象,
我们把它转为一个计算好每个元素左边的1值是连续的个数的矩阵
例如:
{
{0, 0, 0, 1, 1, 1},
{1, 0, 1, 0, 0, 0},
{1, 0, 0, 0, 1, 1},
{0, 0, 1, 1, 1, 1},
{1, 1, 0, 1, 1, 1}};
经过我下面写的循环计算每个left[row][col]的值是由left[row][col - 1]+ 1累加而成,
那我们来看看这个二维数组的最后一列该变成多少呢?
{
{0, 0, 0, 1, 2, 3},
{1, 0, 1, 0, 0, 0},
{1, 0, 0, 0, 1, 2},
{0, 0, 1, 2, 3, 4},
{1, 2, 0, 1, 2, 3}};
所以是3,0,2,4,3
然后再应用LeetCode84号题的解法思路,进行改造,得到如下LeetCode84号题的解.
*/
public class _85_maximal_rectangle {
public int maximalRectangle(char[][] matrix) {
int m = matrix.length;//行数
if (m == 0) return 0;
int n = matrix[0].length;
int[][] left = new int[m][n];
for (int row = 0; row < m; row++) {
for (int col = 0; col < n; col++) {
if (matrix[row][col] == 1) {
left[row][col] = (col == 0 ? 0 : left[row][col - 1]) + 1;
}
}
}
int maxArea = 0;
ArrayDeque<Integer> stack = new ArrayDeque<>();
for (int col = 0; col < n; col++) {//列固定
for (int row = 0; row < m; row++) {//完成一个单调递增栈,栈中存行号索引
while (!stack.isEmpty() && left[row][col] < left[stack.peek()][col]) {
int k = stack.peek();
int countDepth = row - k;
int newBreadth = left[stack.pop()][col];
int countArea = newBreadth * countDepth;
maxArea = Math.max(maxArea, countArea);
}
stack.push(row);
}
while (!stack.isEmpty()) {
int k = stack.peek();
int countDepth = m - k;
int newBreadth = left[stack.pop()][col];
int countArea = countDepth * newBreadth;
maxArea = Math.max(maxArea, countArea);
}
}
return maxArea;
}
public static void main(String[] args) {
_85_maximal_rectangle maximal_rectangle = new _85_maximal_rectangle();
char[][] ints = {
{0, 0, 0, 1, 1, 1},
{1, 0, 1, 0, 0, 0},
{1, 0, 0, 0, 1, 1},
{0, 0, 1, 1, 1, 1},
{1, 1, 0, 1, 1, 1}};
System.out.println(maximal_rectangle.maximalRectangle(ints));
}
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。