11. Container With Most Water

LeetCode задача 11

Задача

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

Подсказки

Метод “Two Pointers”.

Подход

Цель этой задачи - найти пару “стен”, между которыми будет находиться максимальное количество “воды”. Вместимость контейнера определяется двумя факторами: расстоянием между стенками и минимальной высотой из двух стенок.

Идея алгоритма заключается в следующем: начнем с самых “дальних” друг от друга стенок и будем постепенно “сужать” интервал, сдвигая одну из стенок внутрь массива. При этом всегда сдвигаем ту стенку, которая ниже, потому что движение более высокой стенки внутрь не приведёт к увеличению объёма контейнера (меньшая высота ограничивает его).

Этот подход эффективен, потому что мы однократно проходим по всему массиву, каждый раз вычисляя и сравнивая вместимость текущего “контейнера” с максимальной найденной ранее.

Алгоритм

1. Инициализация: Создаем два указателя, один на начале массива и другой на конце.
2. Выбор стенки: Сначала у нас есть весь массив для выбора стенки. Мы можем взять две крайние стенки, так как расстояние между ними максимально.
3. Перемещение указателей: После каждого шага, мы двигаем один из указателей внутрь массива. Указатель на меньшую стенку двигается внутрь, потому что движение указателя на большую стенку не может привести к большему контейнеру.
4. Обновление максимума: На каждом шаге мы проверяем, больше ли текущий контейнер предыдущего максимума. Если да, обновляем максимум.
5. Возврат результата: В конце работы алгоритма, возвращаем размер максимального контейнера.

Решение

def maxArea(height: list[int]) -> int:
    # Инициализация указателей и максимума
    left = 0
    right = len(height) - 1
    max_area = 0

    while left < right:
        min_height = min(height[left], height[right])
        area =  min_height * (right - left)

        max_area = max(max_area, area)

        if height[left] <= height[right]:
            left += 1
        else:
            right -= 1

    return max_area