Max Area of Island

Средняя№695сетка

Дана карта из клеток суши и воды. Клетки суши, которые касаются стороной, — один остров, а его площадь — число его клеток. Нужно найти площадь самого большого острова или 0, если суши нет. На нашей карте 4 строки: # # . #, . . # ., . # # #, # . # . (# — суша) — ответ 5: плюс в середине; у остальных островов 2, 1 и 1 клетка.

695 Max Area of IslandРазбор · 1×

Пример: найти самый большой остров на карте, где он находится третьим и расходится от центра в три стороны.

01230123~~~~~~~best = 0стек вызововвершина справа—
суша, ещё не измеренавода с самого началав стеке вызовов, внутри — size на сейчастекущая клеткасоседняя суша, её измеряем следующейстала водой, ↑ — площадь, которую вернул её вызов

Ни одного острова ещё не измерили: best = 0

01/68
сначала · назад · пуск · шаг
Скорость
1function maxArea(grid):
2 best = 0
3 for each cell (row, col), row by row:
4 if grid[row][col] is land:
5 best = max(best, area(row, col))
6 return best
7
8function area(r, c):
9 grid[r][c] = water // so it is counted once
10 size = 1
11 for each land neighbour (nr, nc):
12 size = size + area(nr, nc)
13 return size
состояние
best
0
row
–
col
–
r
–
c
–
size
–
nr
–
nc
–
нажмите шаг, чтобы вернуться

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

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

  1. Площадь суши, достижимой из клетки, — это 1 за саму клетку плюс площади, достижимые из соседней суши, поэтому каждый вызов складывает то, что вернули его вызовы.
  2. Клетка становится водой, как только в неё входит вызов, поэтому другой вызов её не посчитает, даже там, где ветви острова сходятся.
  3. Каждый остров целиком измеряет один вызов из прохода по карте, поэтому сравнение этих результатов с best находит самый большой.

Сложность

Время O(rows × cols): каждую клетку проходим один раз, и в каждую клетку суши входим один раз. Память O(rows × cols) в худшем случае — на стек вызовов глубиной в один длинный остров.

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

Решить на LeetCode ↗

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