最大正方形

1. 题目描述

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

2. 思路

1. 思路一
   • 暴力
   • 遇到一个1就当成左上角，看能扩充到多大的边长

3. 实现

3.1. 暴力

package main

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

	maxSide := 0
	for row := 0; row < rows; row++ {
		for col := 0; col < cols; col++ {
			side := Min(rows-row, cols-col)
			if matrix[row][col] == '1' && side > maxSide {
				maxSide = Max(maxSide, maxSquare(matrix, row, col, side))
			}
		}
	}

	return maxSide * maxSide
}

// 将data[row][col]作为左上角，判断是否边长为side的正方形
func maxSquare(data [][]byte, row, col, side int) int {
	max := 0
	for currentSide := 0; currentSide < side; currentSide++ {
		for i := 0; i <= currentSide; i++ {
			if data[row+currentSide][col+i] == '0' {
				return max
			}
			if data[row+i][col+currentSide] == '0' {
				return max
			}
		}
		max += 1
	}

	return max
}

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

func Max(data ...int) int {
	max := data[0]
	for i := 1; i < len(data); i++ {
		if data[i] > max {
			max = data[i]
		}
	}
	return max
}

4. 参考

• 221. 最大正方形 - 力扣（LeetCode）