maxArea调用了maxRecFormBoottom函数,就是下面所介绍的
public static int maxRecSize(int [][]map)
{
if(map==null||map.length==0||map[0].length==0)
{
return 0;
}
int maxArea=0;
int [] height=new int[map[0].length];
for(int i=0;i<map.length;++i)
{
for(int j=0;j<map[0].length;j++)
{
height[j]=map[i][j]==0?0:height[j]+1;
}
maxArea=Math.max(maxRecFromBottom(height), maxArea);
}
return maxArea;
}
public static int maxRecFromBottom(int [] height)
{
if(height==null||height.length==0)
{
return 0;
}
int maxArea=0;//最大面积
Stack<Integer>stack=new Stack<Integer>();//从栈底到栈顶从小到大排列
for(int i=0;i<height.length;i++)
//一个数弹出就结算它的面积
//压入当前值
{
while(!stack.isEmpty()&&height[i]<=height[stack.peek()])
//当stack不空且插入的值比栈顶元素要小,height是作为插入的值用的
{
int j=stack.pop();
int k=stack.isEmpty()?-1:stack.peek();//左边界,当该值被弹出,
//它下面没有东西了,左边界就是-1,如果它的下面有东西,那么左边界就是那个数
int curArea=(i-k-1)*height[j];//当前行的面积
maxArea=Math.max(maxArea, curArea);
}
stack.push(i);//如果插入的数小于栈顶就直接插入
}
//遍历完以后栈中还剩一些东西,结算剩下的那些东西
while(!stack.isEmpty())
{
int j=stack.pop();//从栈顶依次弹出
int k=stack.isEmpty()?-1:stack.peek();
int curArea=(height.length-k-1)*height[j];//结算弹出栈顶的面积
maxArea=Math.max(maxArea, curArea);//记录最大面积
}
return maxArea;
}
public static void main(String[] args) {
int [][]map={{1,0,1,1},{1,1,1,1},{1,1,1,0}};
int a=maxRecSize(map);
System.out.println(a);
}