Почему это работает
- Начинаем с самого широкого контейнера: две крайние стенки. Каждый следующий уже, поэтому выиграть он может только высотой.
- Вода поднимается только до нижней стенки. Двигать высокую бессмысленно: ширина падает, а высота не вырастет выше нижней стенки. Поэтому двигаем нижнюю.
- Каждый сдвиг отбрасывает стенку вместе со всеми контейнерами, которые она ещё могла дать, и ни один из них не больше только что измеренного. Значит, лучший контейнер не пропустим.
Сложность
Время O(n): каждый шаг сдвигает одну стенку внутрь, поэтому шагов не больше n − 1. Память O(1): два указателя и лучшая площадь.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗