Что означает поиск двух линий при создании контейнера?

Каков подходящий способ утврждения двух линий с осью x, чтобы образовать контейнер, который может вместить наибольшее количество воды? Как определить оптимальное количество воды, которое может быть содержимо в контейнере?
  • 7 мая 2024 г. 9:10
Ответы на вопрос 2
Поиск двух линий при создании контейнера означает выбор двух точек на графике, которые будут служить боковыми стенками контейнера. 

Для утверждения двух линий с осью x и создания контейнера, который может вместить наибольшее количество воды, можно использовать метод двух указателей (two pointer approach). Этот подход заключается в том, что два указателя будут двигаться от краев контейнера к центру, при этом каждый раз выбирая более высокую из двух стенок контейнера (линий) для увеличения объема воды. 

Оптимальное количество воды, которое может быть содержимо в контейнере, можно определить следующим образом: вычислить разницу в значениях x между двумя линиями и умножить на минимальную из этих двух значений. Это даст площадь контейнера, которая и будет являться объемом воды, который он может вместить.
У вас есть куча вертикальных столбиков с заданными высотами. Вам надо взять 2 столбика так, чтобы между ними было больше всего воды. Они образуют загогулину вроде |____| - это и есть контейнер, в котором может быть вода (если мир двумерный). Например если в примере взять самый левый (1) и самый правый (7) столбики, то высота воды будет 1 (иначе она слева выльется), а ширина будет 8 - итого получается 1*8=8 единиц воды. 

Формально, вам надо найти такие i<j , что min(h[i],h[j])*(j-i) максимально.
Похожие вопросы