Maximal Square

Средняя№221двумерная таблица

В сетке стоят нули и единицы. Нужно найти самый большой квадрат только из единиц и вернуть его площадь. Наш пример: [1, 1, 1, 0], [1, 1, 1, 1], [1, 1, 1, 1], [0, 1, 1, 1]. Самый большой квадрат из единиц — 3 × 3, ответ 9.

221 Maximal SquareРазбор · 1×

Пример: сетка 4 × 4 с нулями в двух углах. Смотрите на (2, 3): слева кончается квадрат 3 × 3, но из-за нуля в (0, 3) сверху только 1, и у (2, 3) выходит 2.

012301231110111111110111
единица сетки, ещё не дошлиноль сеткисторона самого большого квадрата с углом здесьэтот шагнаименьший сосед, берём отсюдасамый большой квадрат

dp[r][c]: сторона самого большого квадрата из единиц, у которого правый нижний угол в (r, c). Сначала везде 0

01/34
сначала · назад · пуск · шаг
Скорость
1function maximalSquare(grid):
2 dp = table of the grid's size, all 0
3 side = 0
4 for each cell (r, c), row by row:
5 if grid[r][c] == 1:
6 up = dp[r - 1][c], or 0 off the grid
7 left = dp[r][c - 1], or 0 off the grid
8 diag = dp[r - 1][c - 1], or 0 off the grid
9 dp[r][c] = 1 + min(up, left, diag)
10 side = max(side, dp[r][c])
11 return side * side
состояние
dp
[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
side
–
r
–
c
–
up
–
left
–
diag
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Квадрат k × k из единиц с углом в (r, c) содержит квадраты (k - 1) × (k - 1), которые кончаются сверху, слева и по диагонали. Поэтому он есть ровно тогда, когда все три клетки дают хотя бы k - 1: dp — это 1 + наименьшая из них.
  2. Наименьшая и ограничивает: в (2, 3) слева 3, по диагонали 2, но сверху 1 — ноль в (0, 3) ломает там любой квадрат побольше.
  3. По строкам все три клетки, которые читает клетка, заполнены раньше неё, а side хранит наибольшее значение, поэтому в конце площадь — side × side.

Сложность

Время O(m × n): каждая клетка один раз читает трёх соседей. Память O(m × n) на таблицу; клетка читает только свою строку и строку над ней, так что хватит двух строк.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.