Поиск контейнера, удерживающего максимальный объём жидкости

Условие

Дан массив целых чисел heights длиной n. На координатной плоскости построены n вертикальных отрезков, где i‑й отрезок соединяет точки (i, 0) и (i, heights[i]). Требуется выбрать две такие линии, которые вместе с осью x образуют сосуд, способный удержать наибольшее количество воды. Необходимо вернуть максимальный объём воды, который может быть содержан этим сосудом. Учтите, что наклонять сосуд нельзя.

Ответ

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

Для неотрицательных высот площадь равна ширине, умноженной на меньшую стенку. Сдвиг более высокой стенки не улучшит результат при той же низкой стенке, поэтому низкую можно отбросить.

def max_area(heights):
    left, right = 0, len(heights) - 1
    best = 0
    while left < right:
        best = max(best, (right - left) * min(heights[left], heights[right]))
        if heights[left] <= heights[right]:
            left += 1
        else:
            right -= 1
    return best

При длине меньше двух результат равен нулю.