题目

给定一个N*N的矩阵matrix，在这个矩阵中只有0和1两种值，返回边框全是1的最大正方形的边长长度。
例如:
01111
01001
01001
01111
01011
其中，边框全是1的最大正方形的大小为4*4，所以返回4。

思路

暴力的方法是对于每个点，判断是否有边长为n,-1,n-2…的正方形图案，
因此复杂度为O(n*n)[共有n*n个点]*O(n)[遍历n个边长的正方形图案]*O(n)[判断该正方形图案是正方形],即O(n^4)
优化的地方在判断是否是正方形的地方，
添加2个二维数组，分别记录当前位置下边和右边1的个数
则判断是否是正方形只需判断左上角下和右1的个数、右上角下方1的个数、左下角右方1的个数
优化后为O(1)
即总的时间复杂度为O(n*n)[共有n*n个点]*O(n)[遍历n个边长的正方形图案]*O(1)[判断该正方形图案是正方形]+O(n*n)[初始化二维数组]=O(n^3)

例如right矩阵，有一行1 1 0 1 1，则right矩阵的值是2 1 2 2 1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public static void setMap(int[][] m, int[][] down, int[][] right){
	for(int i = m.length - 1; i >= 0; i--){
		//最后一行
		right[i][m[0].length - 1] = m[i][m[0].length - 1] == 1 ? 1 : 0;
		for(int j = m[0].length - 2; j >= 0; j-- ){
			//主要看右边的
			if(m[i][j+1]== 1){
				right[i][j] = right[i][j+1] + m[i][j];
			}else{
			//当前值是0，就只加自己的值
				right[i][j] = m[i][j];
			}
		}
	}
	for(int i = m[0].length - 1; i >= 0; i--){
		down[m.length - 1][i] = m[m[0].length - 1][i] == 1 ? 1 : 0;
		for(int j = m.length - 2; j >= 0; j-- ){
			if(m[j+1][i]== 1){
				down[j][i] = down[j+1][i] + m[i][j];
			}else{
				down[j][i] = m[j][i];
			}
		}
	}
	
}
public static int getLen(int[][] m){
	int[][] down = new int[m.length][m[0].length];
	int[][] right = new int[m.length][m[0].length];
	setMap(m, down, right);
	int len = 0;
	for(int i = 0; i < m.length; i++){
		for(int j = 0; j < m[0].length; j++){
			//k为生成的正方形边长
			int x= Math.min(m.length - i, m[0].length - j);
			for(int k = x; k > 0; k--){
				//左上角下和右1的个数、右上角下方1的个数、左下角右方1的个数
				if(m[i][j] == 1 && right[i][j] >= k && down[i][j] >= k && 
						right[i+k-1][j] >= k && down[i][j+k-1] >= k){
					len = Math.max(k, len);
				}
			}
			
		}
	}
	return len;
}

题目

给定一个整型矩阵matrix，其中的值只有0和1两种，求其中全是1的所有矩形区域中，最大的矩形区域为1的数量。
例如:
1110
其中，最大的矩形区域有 3 个 1，所以返回3。
再如:
1011
1111
1110
其中，最大的矩形区域有6个1，所以返回6。

思路

  • 生成height[]
    每行对应一个用height[]，表示以当前行为底，连续的1的个数
    然后把这些数字看成一个柱状图，找到最大的矩形面积,不断更新

  • 找最大面积
    这个找最大面积的过程是依次遍历每个数字，然后分别往左右两边扩，直到遇到比它小的数字就停止，
    这个间距就是矩形的长，宽就是遍历的该数字。
    此过程的时间复杂度是O(1)，即遍历一次就能找到。

具体做法是生成一个栈，栈中存放数字的下标。
当栈空或者即将入栈的元素比栈顶大，就一直入栈。
直到遇到了比栈顶小的元素，此时开始出栈顶，那么出栈元素右边第一个比它小的就是当前元素，左边第一个比他小的就是新的栈顶元素。
这样就找到了每个矩形的面积，更新面积。
然后继续入栈出栈的过程。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public static int getMaxArea(int[][] map){
	int[] height = new int[map[0].length];
	int res = 0;
	//更新height
	for(int i = 0; i < map.length; i++){
		for(int j = 0; j < height.length; j++){
			//height记录的是连续的1的个数
			height[j] = map[i][j] == 0 ? 0 : height[j] + 1;
		}
		res = Math.max(res, fArea(height));
	}
	return res;
}
public static int fArea(int[] a){
	//栈中存放数字的下标
	Stack<Integer> stack = new Stack<Integer>();
	int maxArea = 0;
	//实现一次遍历就找面积
	for(int i = 0; i < a.length; i++){
		//对于栈不空时，当前元素小于等于栈顶时都要出栈，
		while(!stack.empty() && a[i] <= a[stack.peek()]){
			//栈顶出栈，得到矩形的宽a[k]
			int k = stack.pop();
			//左边第一个比a[k]小的值
			int left = stack.empty()? -1: stack.peek();
			//右边第一个比a[k]小的值，同时注意存在相等的状况
			int right = a[k] == a[i] ? i+1 : i;
			//区间是左开右开
			int tmp = (right - left - 1)* a[k];
			maxArea = Math.max(tmp, maxArea);
		}
		stack.push(i);
	}
	//遍历结束后仍然存在元素
	while(!stack.empty()){
		//栈顶出栈，得到矩形的宽a[k]
		int k = stack.pop();
		//栈空时
		int right = stack.empty()? a.length: k + 1;
		int left = stack.empty()? -1: stack.peek();
		//区间是左开右开
		int tmp = (right - left - 1)* a[k];
		maxArea = Math.max(tmp, maxArea);
	}
	return maxArea;
}