Container With Most Water

Средняя№11навстречу

Даны высоты стенок, которые стоят в ряд на расстоянии шага друг от друга. Нужно выбрать две так, чтобы между ними поместилось больше всего воды: расстояние между стенками на высоту нижней из них. Наш пример: высоты [2, 6, 3, 5, 1, 4, 7, 3] — ответ 30, стенки 6 и 7.

11 Container With Most WaterРазбор · 1×

Пример: высоты [2, 6, 3, 5, 1, 4, 7, 3]. Синее — вода между двумя стенками, пунктир — лучший контейнер на этот момент.

2061325314457637left
две стенкиотброшенылучшая пара

left — на первой стенке, высота 2

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

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

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

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

Сложность

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

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

Решить на LeetCode ↗

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