Войти Регистрация
Алгоритмы

10. Сколько воды соберётся между столбиками

Сложная

Дан массив неотрицательных чисел — высоты столбиков шириной 1. После дождя вода собирается в ямах между столбиками. Сколько единиц воды останется?

В работе: Сколько воды останется на плоской кровле с перепадами высот после ливня.

Пример 1

Ввод
heights = [3, 0, 2, 0, 4]
Вывод
7

Над столбиками 1, 2, 3 вода стоит на уровне 3: 3 + 1 + 3.

Пример 2

Ввод
heights = [1, 2, 3]
Вывод
0

Высоты растут — вода стекает.

Ограничения

  • 0 ≤ длина ≤ 300 000 (в JavaScript — до 2 000 000)
  • 0 ≤ высота ≤ 10⁵
  • Лимит — 1 с на тест.
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def trap(heights: list[int]) -> int:
Два указателяМассивцельO(n)

Источник: отчёт о Яндексе, 2023. Условие пересказано своими словами.

Давали на собеседовании? Ответов пока мало — ваш поможет.