求最大子矩阵的大小

求最大子矩阵的大小
求最大子矩阵的大小
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);
		}
上一篇:fork() 函数的使用


下一篇:C++数据结构之栈(十三)