public static int maximalRectangle(char[][] matrix) {

		 int rowNum=matrix.length;
if(rowNum==0)
return 0;
int columnNum=matrix[0].length; int[][] height=new int[rowNum][columnNum+1];
int maxarea=0; for(int i=0;i<rowNum;i++)
{
for(int j=0;j<columnNum;j++)
{
int k=i;
height[i][j]=0;
while(k>=0&&j<columnNum)
{
if(matrix[k][j]=='1')
height[i][j]++;
else
break;
k--;
} }
height[i][columnNum]=-1;
} Stack<Integer> stack=new Stack<>();
for(int i=0;i<rowNum;i++)
{
for(int j=0;j<=columnNum;j++)
{
int a=height[i][j];
int b=stack.isEmpty()?-1:stack.peek();
if(stack.isEmpty()||height[i][j]>=height[i][stack.peek()])
stack.push(j);
else
{ int tempPop=stack.pop();
maxarea=Math.max(maxarea, height[i][tempPop]*(stack.isEmpty()? j:j-1-stack.peek()));
j--;
}
}
stack.clear();
} return maxarea; }

题目:

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.

也就是说,给一个仅仅有0和1的2维矩阵,求当中1可以组成的最大四方形面积

解题:

这题能够看作是前面一题(LeetCode84)的拓展,前面一题中输入的是一个数组,数组每个元素的值看作的矩形的高度,在这题中先对矩阵做一个处理。对矩阵的元素计算其高度,处理完之后得到一个每个原矩阵元素的高度矩阵,把这个矩阵当作输入就和前面一题是类似了。

代码:

05-11 22:17
查看更多