11. Бассейн наибольшего объёма (Container With Most Water)

Задание.

Вам задается целочисленная высота массива длиной n. Существует n вертикальных линий, нарисованных таким образом, что две конечные точки i-й линии равны (i, 0) и (i, height[i]).

Найдите две линии, которые вместе с осью x образуют контейнер, такой, чтобы в контейнере было больше всего воды.

Верните максимальное количество воды, которое может храниться в контейнере.

Обратите внимание, что вы не можете наклонять контейнер.

Пример 1.

Входные данные: height = [1,8,6,2,5,4,8,3,7]

Результат: 49

Пояснение:

Приведенные выше вертикальные линии представлены массивом [1,8,6,2,5,4,8,3,7]. В этом случае максимальная площадь воды (синяя секция), которую может вместить контейнер, равна 49.

Пример 2.

Входные данные: height = [1,1]

Результат: 1

Решение.

class Solution {
public:
    int maxArea(vector<int>& height) {
        
        int i = 0, j = height.size()-1;
        int volume, bigger_volume = 0;

        while(i < j) {
            // вычисляем объем
            volume = (j-i) * min(height[i], height[j]);

            // если нужно, обновляем максимальное значение объема
            if(volume > bigger_volume) {
                bigger_volume = volume;
            }

            // если правая граница выше, двигаемся вправо
            // иначе двигаемся влево
            if(height[j] > height[i]) {
                i++;
            } else {
                j--;
            }
        }

        return bigger_volume;
    }
};