Trapping Rain Water

Сложная№42навстречу

Даны высоты столбиков шириной 1, которые стоят вплотную друг к другу. Прошёл дождь: сколько воды осталось между столбиками? Наш пример: высоты [3, 0, 1, 4, 0, 2, 1, 3] — 11 единиц воды.

42 Trapping Rain WaterРазбор · 1×

Пример: высоты [3, 0, 1, 4, 0, 2, 1, 3]. Синее — уже посчитанная вода; пунктир — leftMax и rightMax, самый высокий столбик, пройденный с каждого конца.

3014021301234567left
ещё не дошлипод указателемвода над ним посчитана

left — на первом столбике, высота 3

01/54
сначала · назад · пуск · шаг
Скорость
1function trap(height):
2 left = 0
3 right = len(height) - 1
4 leftMax = 0; rightMax = 0
5 water = 0
6 while left <= right:
7 leftMax = max(leftMax, height[left])
8 rightMax = max(rightMax, height[right])
9 if leftMax <= rightMax:
10 water = water + leftMax - height[left]
11 left = left + 1
12 else:
13 water = water + rightMax - height[right]
14 right = right - 1
15 return water
состояние
left
0
right
–
leftMax
–
rightMax
–
water
–
историянажмите шаг, чтобы вернуться

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

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

  1. Вода над столбиком поднимается до меньшей из двух стенок: самого высокого столбика слева от него и самого высокого справа. Выше — перельётся через меньшую.
  2. Если leftMax ≤ rightMax, справа уже есть стенка не ниже leftMax, а настоящий максимум справа может быть только выше. Значит, над left вода — ровно leftMax минус его высота, что бы ни стояло между указателями. Справа — так же, зеркально.
  3. Поэтому двигаем сторону с меньшим максимумом: воду над её столбиком мы уже знаем точно, и каждый шаг закрывает один столбик навсегда.

Сложность

Время O(n): каждый шаг закрывает один столбик и сдвигает один указатель, всего n шагов. Память O(1): два указателя, два максимума и сумма, без массивов максимумов для каждого столбика.

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

Решить на LeetCode ↗

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