Pacific Atlantic Water Flow

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

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

417 Pacific Atlantic Water FlowРазбор · 1×

Пример: найти клетки острова 3 × 3, дождь из которых стекает в оба океана, поднимаясь от берега каждого океана.

012012123452311pacificсверху и слева012012123452311atlanticснизу и справастек вызововвершина справа—в обоих—
подъём этого океана не дошёлв стеке вызововтекущая клеткасосед не ниже: поднимаемся к немусосед ниже: его вода сюда не подниметсядошли: вода отсюда течёт в этот океан

pacific = пустое множество: клетки, вода из которых доходит до Тихого океана. Заполним его, поднимаясь от берега, а не спускаясь из каждой клетки

01/67
сначала · назад · пуск · шаг
Скорость
1function pacificAtlantic(heights):
2 pacific = empty set
3 atlantic = empty set
4 for each cell (row, col) on the top or left edge, not in pacific:
5 climb(row, col, pacific)
6 for each cell (row, col) on the bottom or right edge, not in atlantic:
7 climb(row, col, atlantic)
8 return cells in both pacific and atlantic
9
10function climb(r, c, ocean):
11 ocean.add((r, c))
12 for each neighbour (nr, nc) not in ocean:
13 if heights[nr][nc] >= heights[r][c]:
14 climb(nr, nc, ocean)
состояние
row
–
col
–
ocean
–
r
–
c
–
nr
–
nc
–
нажмите шаг, чтобы вернуться

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

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

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

Сложность

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

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

Решить на LeetCode ↗

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