Контейнер с наибольшим количеством воды

Контейнер с наибольшим количеством воды

Задача о контейнере (Container with Most Water) — это классический алгоритмическая задача, проверяющая умение применять метод двух указателей (Two Pointers) для оптимизации решения. На первый взгляд может показаться, что нужно проверить все пары, но существует умный линейный подход.

Понимание задачи

У нас есть массив высот. Площадь контейнера = ширина × минимальная высота из двух выбранных линий.

Массив: [1, 8, 6, 2, 5, 4, 8, 3, 7]
Индексы: 0  1  2  3  4  5  6  7  8

Если выбираем индексы 1 и 8 (высоты 8 и 7):
Ширина = 8 - 1 = 7
Высота = min(8, 7) = 7
Площадь = 7 × 7 = 49

Подход 1: Брутфорс O(n²)

Проверяем все возможные пары линий:

def maxArea_Brute(height):
    max_area = 0
    n = len(height)
    
    for i in range(n):
        for j in range(i + 1, n):
            width = j - i
            h = min(height[i], height[j])
            area = width * h
            max_area = max(max_area, area)
    
    return max_area

print(maxArea_Brute([1, 8, 6, 2, 5, 4, 8, 3, 7]))  # 49

Сложность:

• Временная: O(n²) — два вложенных цикла
• Пространственная: O(1) — только переменные

Подход 2: Двухуказательный метод O(n) ⭐

Это оптимальное решение. Идея:

• Начинаем с самого широкого контейнера (начало и конец)
• Двигаем указатель, указывающий на более короткую линию
• Так как площадь зависит от минимальной высоты, имеет смысл двигать более короткий указатель

def maxArea(height):
    left = 0
    right = len(height) - 1
    max_area = 0
    
    while left < right:
        # Вычисляем текущую площадь
        width = right - left
        h = min(height[left], height[right])
        area = width * h
        max_area = max(max_area, area)
        
        # Двигаем указатель с меньшей высотой
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    
    return max_area

print(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]))  # 49

Сложность:

• Временная: O(n) — один проход по массиву
• Пространственная: O(1) — только два указателя

Пошаговый пример выполнения

Массив: [1, 8, 6, 2, 5, 4, 8, 3, 7]

Итерация 1:
left=0 (высота 1), right=8 (высота 7)
ширина = 8, высота = min(1, 7) = 1
площадь = 8 × 1 = 8
1 < 7, двигаем left → left=1

Итерация 2:
left=1 (высота 8), right=8 (высота 7)
ширина = 7, высота = min(8, 7) = 7
площадь = 7 × 7 = 49 ← Максимум!
7 < 8, двигаем right → right=7

Итерация 3:
left=1 (высота 8), right=7 (высота 3)
ширина = 6, высота = min(8, 3) = 3
площадь = 6 × 3 = 18
3 < 8, двигаем right → right=6

Итерация 4:
left=1 (высота 8), right=6 (высота 8)
ширина = 5, высота = min(8, 8) = 8
площадь = 5 × 8 = 40
8 = 8, двигаем right → right=5

Итерация 5:
left=1 (высота 8), right=5 (высота 4)
ширина = 4, высота = min(8, 4) = 4
площадь = 4 × 4 = 16
4 < 8, двигаем right → right=4

Итерация 6:
left=1 (высота 8), right=4 (высота 5)
ширина = 3, высота = min(8, 5) = 5
площадь = 3 × 5 = 15
5 < 8, двигаем right → right=3

Итерация 7:
left=1 (высота 8), right=3 (высота 2)
ширина = 2, высота = min(8, 2) = 2
площадь = 2 × 2 = 4
2 < 8, двигаем right → right=2

left=1, right=2: left < right ✓

Итерация 8:
left=1 (высота 8), right=2 (высота 6)
ширина = 1, высота = min(8, 6) = 6
площадь = 1 × 6 = 6
6 < 8, двигаем right → right=1

left=1, right=1: left < right ✗ → Выход

Максимальная площадь: 49

Почему двухуказательный метод работает?

Это доказывается методом исключения:

Если мы имеем пару (left, right) и height[left] < height[right]:

- Если мы двигаем right влево (к right-1):
  - Ширина уменьшается: (right-1) - left < right - left
  - Высота не может быть больше min(height[left], height[right-1])
  - В лучшем случае высота = height[left] (если height[right-1] >= height[left])
  - Но даже с той же высотой, площадь меньше из-за меньшей ширины
  
- Поэтому имеет смысл двигать left вправо (к left+1):
  - Ширина всё ещё уменьшается
  - Но ПОТЕНЦИАЛЬНО высота может увеличиться (если height[left+1] > height[left])
  - Это может дать нам лучшую площадь

Оптимизированная версия с комментариями

def maxArea_Optimized(height):
    """
    Найти максимальную площадь контейнера.
    
    Args:
        height: List[int] - массив высот линий
    
    Returns:
        int - максимальная площадь
    """
    if not height or len(height) < 2:
        return 0
    
    left = 0
    right = len(height) - 1
    max_area = 0
    
    while left < right:
        # Текущая площадь
        current_height = min(height[left], height[right])
        current_width = right - left
        current_area = current_height * current_width
        
        # Обновляем максимум
        max_area = max(max_area, current_area)
        
        # Двигаем указатель на более короткую линию
        # Это единственное, что имеет смысл, так как
        # площадь ограничена меньшей высотой
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    
    return max_area

Сравнение подходов

Тестирование

def test_max_area():
    assert maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]) == 49
    assert maxArea([1, 1]) == 1
    assert maxArea([4, 3, 2, 1, 4]) == 16
    assert maxArea([2, 3, 4, 5, 18, 17, 6]) == 17
    assert maxArea([]) == 0
    assert maxArea([5]) == 0
    print("All tests passed!")

test_max_area()

Расширение задачи

Вариант 1: найти не только площадь, но и индексы линий

def maxArea_WithIndices(height):
    left = 0
    right = len(height) - 1
    max_area = 0
    best_left, best_right = 0, 0
    
    while left < right:
        area = min(height[left], height[right]) * (right - left)
        if area > max_area:
            max_area = area
            best_left, best_right = left, right
        
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    
    return max_area, best_left, best_right

Вариант 2: найти все пары с максимальной площадью

def maxArea_AllPairs(height):
    left = 0
    right = len(height) - 1
    max_area = 0
    pairs = []
    
    while left < right:
        area = min(height[left], height[right]) * (right - left)
        if area > max_area:
            max_area = area
            pairs = [(left, right)]
        elif area == max_area:
            pairs.append((left, right))
        
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    
    return max_area, pairs

Практические применения

• Оптимизация ёмкостей — физические контейнеры
• Анализ финансовых данных — максимальная прибыль между двумя точками
• Проектирование бассейнов — оптимальная конфигурация

Ключевые выводы

✅ Двухуказательный метод — мощная техника для линейных задач

✅ Интуиция: если одна линия короче, двигаем её, ища более высокую

✅ O(n) против O(n²) — разница в 1000 раз на больших входах