221.M 最大正方形

题目

https://leetcode-cn.com/problems/maximal-square/

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

示例 1：

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] 
输出：4 

示例 2：

输入：matrix = [["0","1"],["1","0"]] 
输出：1 

示例 3：

输入：matrix = [["0"]] 
输出：0

提示：

• m == matrix.length

• n == matrix[i].length

• 1 <= m, n <= 300

• matrix[i][j] 为 '0' 或 '1'

解题思路

动态规划。状态转移方程：dp(i,j)=min(dp(i−1,j),dp(i−1,j−1),dp(i,j−1))+1，其中dp(i,j)表示以坐标(i,j)为右下角的正方形的最大边长。

实现代码

func maximalSquare(matrix [][]byte) int {
	rows := len(matrix)
	cols := len(matrix[0])

	dp := make([][]int, rows)
	for i := 0; i < rows; i++ {
		dp[i] = make([]int, cols)
	}

	maxLen := 0
	for i := 0; i < rows; i++ {
		for j := 0; j < cols; j++ {
			if matrix[i][j] == '1' {
				if i == 0 || j == 0 {
					dp[i][j] = 1
				} else {
					dp[i][j] = min(min(dp[i][j-1], dp[i-1][j-1]), dp[i-1][j]) + 1
				}
				if dp[i][j] > maxLen {
					maxLen = dp[i][j]
				}
			}
		}
	}

	return maxLen * maxLen
}

func min(a, b int) int {
	if a <= b {
		return a
	}
	return b
}