Сложность: medium
Дана бинарная матрица размером m x n, заполненная 0 и 1. Найдите наибольший квадрат, содержащий только 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
👨💻 Алгоритм:
1⃣Инициализировать 1D массив dp с нулями, чтобы хранить промежуточные результаты для каждого столбца, а также переменные maxsqlen для максимальной длины квадрата и prev для предыдущего значения.
2⃣Пройти по каждому элементу матрицы. Если текущий элемент равен '1', обновить dp[j] по формуле dp[j]=min(dp[j−1],prev,dp[j])+1 и обновить maxsqlen. Если текущий элемент равен '0', установить dp[j] в 0. Обновить prev на значение dp[j] перед его изменением.
3⃣По завершении пройти по всем строкам и столбцам, вернуть квадрат maxsqlen как площадь наибольшего квадрата.
😎 Решение:
class Solution:
def maximalSquare(self, matrix):
rows = len(matrix)
cols = len(matrix[0]) if rows > 0 else 0
dp = [0] * (cols + 1)
maxsqlen = 0
prev = 0
for i in range(1, rows + 1):
for j in range(1, cols + 1):
temp = dp[j]
if matrix[i - 1][j - 1] == "1":
dp[j] = min(min(dp[j - 1], prev), dp[j]) + 1
maxsqlen = max(maxsqlen, dp[j])
else:
dp[j] = 0
prev = temp
return maxsqlen * maxsqlen
Ставь 👍 и забирай 📚 Базу знаний