[LeetCode] 221. Maximal Square

轉自LeetCode

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Example:

Input: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

<Solution>

想法如下

• 目標是要找出面積最大的正方形，檢查方式是當目前的位置是 1 時，往對角線右下的方向移動一格，然後檢查該列和該行，到剛剛移動前的行和列，路途中間有沒有都是 1，是的話就是一個正方形。繼續往對角線右下方前進，直到不滿足正方形的條件，並記錄該正方形的邊長

• 上面這點的概念，可以用下列公式來找到每個正方形的邊長

        dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

• 所以這題是可以用 dp 的方式來解的，過程當中並紀錄最長邊長即可找到答案

code 如下

Java(參考解答)

	class Solution {
	public int maximalSquare(char[][] matrix) {
	final int row = matrix.length;
	final int col = row > 0 ? matrix[0].length : 0;
	int[][] dp = new int[row+1][col+1];
	int longestLen = Integer.MIN_VALUE;
	for(int r = 1; r <= row; r++) {
	for(int c = 1; c <= col; c++) {
	if(matrix[r-1][c-1] == '1') {
	dp[r][c] = Math.min(Math.min(dp[r-1][c], dp[r][c-1]), dp[r-1][c-1]) + 1;
	longestLen = Math.max(longestLen, dp[r][c]);
	}
	}
	}
	return longestLen * longestLen;
	}
	}

view raw maximalSquare.java hosted with ❤ by GitHub

kotlin

	class Solution {
	fun maximalSquare(matrix: Array<CharArray>): Int {
	val dp = Array(matrix.size+1) { IntArray(matrix[0].size+1) {0} }
	var longestLen = Int.MIN_VALUE
	for(r in 1..matrix.size) {
	for(c in 1..matrix[0].size) {
	if(matrix[r-1][c-1] == '1') {
	dp[r][c] = Math.min(Math.min(dp[r-1][c], dp[r][c-1]), dp[r-1][c-1]) + 1
	longestLen = Math.max(longestLen, dp[r][c])
	}
	}
	}
	return longestLen*longestLen
	}
	}

view raw maximal_square.kt hosted with ❤ by GitHub