Пример решения задачи #11. Python LeetCode, Контейнер с большим количеством воды

Вариант решения задачи на языке программирования Python с LeetCode.
Категория: Алгоритмы.
Название задачи: Контейнер с большим количеством воды.
Сложность: Средняя.
Статус решения: "Решено".

Условие задачи:
Вам дан целочисленный массив высотой длины n. Нарисовано n вертикальных линий, конечными точками которых являются (i, 0) и (i, высота[i]).

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

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

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

Решение:

Python

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        # Инициализируем два указателя: левый (left) и правый (right), а также переменную для хранения максимальной площади (max_area)
        left = 0
        right = len(height) - 1
        max_area = 0

        # Используем двухуказательный подход для нахождения максимальной площади
        while left < right:
            # Вычисляем текущую ширину контейнера
            width = right - left
            # Вычисляем текущую площадь, ограничиваясь меньшей из высот двух указателей
            current_area = width * min(height[left], height[right])
            # Обновляем максимальную площадь, если текущая больше
            max_area = max(max_area, current_area)

            # Двигаем указатели: уменьшаем меньшую высоту для возможного увеличения площади
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        # Возвращаем максимальную площадь
        return max_area

Объяснение кода

Инициализация указателей и переменной для площади:
Мы используем два указателя left (начало массива) и right (конец массива), чтобы проверять все возможные пары линий, начиная с самых крайних. max_area инициализируем значением 0, так как это минимально возможная площадь.

Основная логика:
В цикле while мы продолжаем сравнивать линии, пока указатели не встретятся.

На каждой итерации:
1) Вычисляем ширину контейнера как расстояние между указателями: width = right - left.
2) Определяем минимальную высоту из двух линий: min(height[left], height[right]), так как именно она ограничивает высоту воды.
3) Вычисляем текущую площадь: current_area = width * min(height[left], height[right]).
4) Сравниваем текущую площадь с максимальной, и если она больше, обновляем max_area.

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

Возвращаем результат:
После завершения цикла возвращаем max_area, что и будет ответом.

Источник решения: hdhai.com