面试题4——矩阵最大正方形边长

package com.harrison.class01;

public class Code04_MaxOneBorderSize {
	public static int getMaxSize(int[][] m) {
		// 两个辅助数组的意义：
		// 记录在原矩阵m中每个格子连同自己格子在内，往右和往左最多的1的个数
		int[][] right=new int[m.length][m[0].length];
		int[][] down=new int[m.length][m[0].length];
		setBorderMap(m, right, down);
		// 矩形有可能是长方形，所以枚举边长的时候选择边长较小的边
		for(int size=Math.min(m.length,m[0].length); size!=0; size--) {
			if(hasSizeOfBorder(size, right, down)) {
				return size;
			}
		}
		return 0;
	}

	public static void setBorderMap(int[][] m, int[][] right, int[][] down) {
		int r = m.length;
		int c = m[0].length;
		// 两个辅助数组的右下角位置
		if (m[r - 1][c - 1] == 1) {
			right[r - 1][c - 1] = 1;
			down[r - 1][c - 1] = 1;
		}
		// 两个辅助数组的最后一列：从下往上填
		for (int i = r - 2; i != -1; i--) {
			if (m[i][c - 1] == 1) {
				right[i][c - 1] = 1;
				down[i][c - 1] = down[i + 1][c - 1] + 1;
			}
		}
		// 两个辅助数组的最后一行：从右往左填
		for (int i = c - 2; i != -1; i--) {
			if (m[r - 1][i] == 1) {
				right[r - 1][i] = right[r - 1][i + 1] + 1;
				down[r - 1][i] = 1;
			}
		}
		// 剩下的格子，从下往上，从右往左填
		for (int i = r - 2; i != -1; i--) {
			for (int j = c - 2; j != -1; j--) {
				if (m[i][j] == 1) {
					right[i][j] = right[i][j + 1] + 1;
					down[i][j] = down[i + 1][j] + 1;
				}
			}
		}
	}
	
	public static boolean hasSizeOfBorder(int size,int[][] right,int[][] down) {
		for(int i=0; i!=right.length-size+1; i++) {
			for(int j=0; j!=right[0].length-size+1; j++) {
				if(right[i][j]>=size && down[i][j]>=size
						&& right[i+size-1][j]>=size
						&& down[i][j+size-1]>=size) {
					return true;
				}
			}
		}
		return false;
	}

	public static int[][] generateRandom01Matrix(int rowSize, int colSize) {
		int[][] res = new int[rowSize][colSize];
		for (int i = 0; i != rowSize; i++) {
			for (int j = 0; j != colSize; j++) {
				res[i][j] = (int) (Math.random() * 2);
			}
		}
		return res;
	}

	public static void printMatrix(int[][] matrix) {
		for (int i = 0; i != matrix.length; i++) {
			for (int j = 0; j != matrix[0].length; j++) {
				System.out.print(matrix[i][j] + " ");
			}
			System.out.println();
		}
	}
	
	public static void main(String[] args) {
		int[][] matrix=generateRandom01Matrix(7, 8);
		System.out.println(matrix.length);
		System.out.println(matrix[0].length);
		printMatrix(matrix);
		System.out.println(getMaxSize(matrix));
	}
}