写了一个N^2的。
public int maximalRectangle(char[][] matrix)
{
if(matrix==null || matrix.length==0)
return 0;
int m=matrix.length;
int n=matrix[0].length;
int[] height=new int[n];
int max=0;
for(int i=0;i{
for(int j=0;jif(matrix[i][j]=='1')
height[j]++;
else
height[j]=0;
max=Math.max(max,largestRectangleArea(height));
}
return max;
}
public int largestRectangleArea(int[] height)
{
class Ele
{
int id;
int height;
public Ele(int _id, int _height)
{
id = _id;
height = _height;
}
}
int max = 0;
Stack stack = new Stack();
int i = 0;
for (i = 0; i < height.length; i++)
{
if (stack.isEmpty() || stack.peek().height < height[i])
stack.add(new Ele(i, height[i]));
else if (stack.peek().height > height[i])
{
int prev = 0;
while (!stack.empty() && stack.peek().height > height[i])
{
Ele e = stack.pop();
max = Math.max(max, e.height * (i - e.id));
prev = e.id;
}
stack.add(new Ele(prev, height[i]));
}
}
while (!stack.empty())
{
Ele e = stack.pop();
max = Math.max(max, e.height * (i - e.id));
}
return max;
}
