221. Maximal Square

Medium
Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
Example 1:
​
​
Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output:
4
Example 2:
​
​
Input: matrix = [["0","1"],["1","0"]]
Output:
1
Example 3:
Input: matrix = [["0"]]
Output:
0
Constraints:
  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 300
  • matrix[i][j] is '0' or '1'.

解題

func maximalSquare(matrix [][]byte) int {
side := 0
​
dp := make([][]int, 0)
for i := 0 ; i < len(matrix); i++ {
dp = append(dp, make([]int, len(matrix[0])))
}
​
for i := 0 ; i < len(matrix); i++ {
dp[i][0] = int(matrix[i][0] - '0')
if dp[i][0] > side {
side = dp[i][0]
}
}
​
for i := 0 ; i < len(matrix[0]); i++ {
dp[0][i] = int(matrix[0][i] - '0')
if dp[0][i] > side {
side = dp[0][i]
}
}
​
for i:=1; i<len(matrix); i++ {
for j:=1; j<len(matrix[0]); j++ {
if matrix[i][j] == '0' {
dp[i][j] = 0
} else {
dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1
}
​
if dp[i][j] > side {
side = dp[i][j]
}
}
}
​
return side * side
}
​
func min(a, b int) int {
if a < b { return a }
return b
}
​