Контейнер с водой: разбор задачи

Почему эта задача важна?

Задача "Контейнер с водой" позволяет оценить:

• 🧠 Умение работать с алгоритмом двух указателей
• ⚡ Навыки оптимизации решения от квадратичной до линейной сложности
• 🎯 Понимание принципов "жадных" алгоритмов
• 🔍 Способность визуализировать геометрические задачи и находить оптимальные решения

Постановка задачи

Формулировка:

Дан целочисленный массив heights, где heights[i] представляет высоту i-го столбца. Вы можете выбрать любые два столбца для формирования контейнера. Верните максимальное количество воды, которое может вместить контейнер.

Примечание: Количество воды, которое может вместить контейнер, определяется как площадь прямоугольника, ширина которого - расстояние между столбцами, а высота - высота более низкого столбца.

Примеры:

// Первый пример ✅
Input: heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49
Объяснение: В данном случае максимальная площадь воды (49) будет между столбцами 
             с индексами 1 и 8 (высоты 8 и 7). Площадь = min(8, 7) * (8 - 1) = 7 * 7 = 49.

// Второй пример ✅
Input: heights = [1, 1]
Output: 1
Объяснение: Между двумя столбцами можно вместить 1 единицу воды.
             Площадь = min(1, 1) * (1 - 0) = 1 * 1 = 1.

Ограничения:

• 2 <= heights.length <= 10^5
• 0 <= heights[i] <= 10^4

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

Подходы к решению

Решение 1: Наивный подход (перебор всех пар) 🔍

function maxArea(heights) {
  let maxWater = 0;
  
  for (let i = 0; i < heights.length; i++) {
    for (let j = i + 1; j < heights.length; j++) {
      // Вычисляем площадь контейнера между i и j
      const width = j - i;
      const height = Math.min(heights[i], heights[j]);
      const area = width * height;
      
      // Обновляем максимальную площадь
      maxWater = Math.max(maxWater, area);
    }
  }
  
  return maxWater;
}

Анализ решения:

✅ Простая реализация и очевидная логика

✅ Гарантированно находит оптимальное решение

❌ Временная сложность O(n²), где n - длина массива

❌ Неэффективен для больших массивов

Решение 2: Метод двух указателей (оптимальное решение) 🚀

function maxArea(heights) {
  let maxWater = 0;
  let left = 0;
  let right = heights.length - 1;
  
  while (left < right) {
    // Вычисляем площадь контейнера между left и right
    const width = right - left;
    const height = Math.min(heights[left], heights[right]);
    const area = width * height;
    
    // Обновляем максимальную площадь
    maxWater = Math.max(maxWater, area);
    
    // Передвигаем указатель, указывающий на меньшую высоту
    if (heights[left] < heights[right]) {
      left++;
    } else {
      right--;
    }
  }
  
  return maxWater;
}

Характеристики:

✅ Оптимальная временная сложность O(n)

✅ Пространственная сложность O(1)

✅ Эффективно находит оптимальное решение за один проход

✅ Использует "жадный" подход для выбора направления движения указателей

Решение 3: Оптимизированный метод двух указателей с ранним выходом 🔧

function maxArea(heights) {
  let maxWater = 0;
  let left = 0;
  let right = heights.length - 1;
  
  while (left < right) {
    // Вычисляем площадь текущего контейнера
    const width = right - left;
    const height = Math.min(heights[left], heights[right]);
    const area = width * height;
    
    maxWater = Math.max(maxWater, area);
    
    // Если осталось мало итераций и максимальная возможная площадь
    // не превысит текущую максимальную, можно завершить поиск
    if (width <= 2 || (right - left - 2) * Math.max(...heights) <= maxWater) {
      break;
    }
    
    // Двигаем указатель с меньшей высотой
    if (heights[left] < heights[right]) {
      // Пропускаем все столбцы с высотой не больше текущей
      const currentHeight = heights[left];
      while (left < right && heights[left] <= currentHeight) {
        left++;
      }
    } else {
      // Пропускаем все столбцы с высотой не больше текущей
      const currentHeight = heights[right];
      while (left < right && heights[right] <= currentHeight) {
        right--;
      }
    }
  }
  
  return maxWater;
}

Преимущества и недостатки:

✅ Временная сложность остается O(n), но с оптимизациями для определенных случаев

✅ Ранний выход для случаев, когда улучшение невозможно

❌ Более сложная реализация

❌ Оптимизации могут не дать значительного прироста на случайных данных

Решение 4: Подход с использованием стека (альтернативный подход) 📚

function maxArea(heights) {
  // Замечание: этот подход менее эффективен для данной конкретной задачи,
  // но демонстрирует альтернативный способ мышления
  
  let maxWater = 0;
  const stack = [];
  
  for (let i = 0; i < heights.length; i++) {
    while (stack.length > 0 && heights[i] > heights[stack[stack.length - 1]]) {
      const height = heights[stack.pop()];
      const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
      maxWater = Math.max(maxWater, height * width);
    }
    stack.push(i);
  }
  
  // Обрабатываем оставшиеся элементы в стеке
  const lastIndex = heights.length - 1;
  while (stack.length > 0) {
    const height = heights[stack.pop()];
    const width = stack.length === 0 ? lastIndex : lastIndex - stack[stack.length - 1];
    maxWater = Math.max(maxWater, height * width);
  }
  
  return maxWater;
}

Особенности:

❌ Не самый подходящий подход для этой конкретной задачи

✅ Демонстрирует использование стека для решения задач с контейнерами

❌ Временная сложность O(n), но константы больше, чем у решения с двумя указателями

❌ Сложнее для понимания и реализации

Почему работает решение с двумя указателями?

Интуиция за алгоритмом двух указателей следующая:

1. Начинаем с максимально широкого контейнера (левый и правый край массива).
2. Площадь ограничена высотой меньшего из двух столбцов.
3. Если мы сдвинем указатель, указывающий на более высокий столбец, ширина контейнера уменьшится, а высота останется той же или станет меньше. Это гарантированно приведет к уменьшению площади.
4. Поэтому логично сдвигать указатель, указывающий на меньший столбец, в надежде найти более высокий столбец, который мог бы увеличить площадь, несмотря на уменьшение ширины.

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

Рекомендации по решению 💡

1. Выбор метода решения:

   • 🚀 Метод двух указателей - оптимальный выбор для этой задачи
   • 📝 Важно понимать, почему мы всегда сдвигаем указатель с меньшей высотой
   • 🧮 Не стоит тратить время на реализацию наивного решения для больших входных данных

2. Важные моменты:

   • 📝 Площадь контейнера вычисляется как ширина × минимальная высота
   • 🔄 Правильная стратегия передвижения указателей - ключ к эффективному решению
   • 📊 Не забывайте учитывать краевые случаи (например, когда высоты равны)

Распространённые ошибки

1. 🤦‍♂️ Неправильное вычисление ширины контейнера (забывание учесть разницу индексов)
2. 😅 Некорректная стратегия движения указателей (например, всегда двигать левый)
3. 🐛 Забывание обновить максимальную площадь после нахождения нового кандидата

Визуализация алгоритма с двумя указателями

Рассмотрим процесс решения на примере heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]:

Начальное состояние:
Указатели: left = 0 (высота 1), right = 8 (высота 7)
Площадь = min(1, 7) * (8 - 0) = 1 * 8 = 8
Максимальная площадь = 8

Шаг 1: Двигаем left (т.к. heights[left] < heights[right])
Указатели: left = 1 (высота 8), right = 8 (высота 7)
Площадь = min(8, 7) * (8 - 1) = 7 * 7 = 49
Максимальная площадь = 49

Шаг 2: Двигаем right (т.к. heights[right] < heights[left])
Указатели: left = 1 (высота 8), right = 7 (высота 3)
Площадь = min(8, 3) * (7 - 1) = 3 * 6 = 18
Максимальная площадь = 49

Шаг 3: Двигаем right (т.к. heights[right] < heights[left])
Указатели: left = 1 (высота 8), right = 6 (высота 8)
Площадь = min(8, 8) * (6 - 1) = 8 * 5 = 40
Максимальная площадь = 49

Шаг 4: Можем двигать любой указатель, т.к. высоты равны, двигаем left
Указатели: left = 2 (высота 6), right = 6 (высота 8)
Площадь = min(6, 8) * (6 - 2) = 6 * 4 = 24
Максимальная площадь = 49

... (продолжаем процесс)

Итоговый результат: 49

Оптимизации

Пропуск заведомо неоптимальных кандидатов

function maxArea(heights) {
  let maxWater = 0;
  let left = 0;
  let right = heights.length - 1;
  
  while (left < right) {
    const width = right - left;
    const height = Math.min(heights[left], heights[right]);
    maxWater = Math.max(maxWater, width * height);
    
    // Если текущая высота ограничивает площадь, нет смысла
    // рассматривать столбцы с меньшей или равной высотой
    if (heights[left] < heights[right]) {
      const currentHeight = heights[left];
      while (left < right && heights[left] <= currentHeight) {
        left++;
      }
    } else {
      const currentHeight = heights[right];
      while (left < right && heights[right] <= currentHeight) {
        right--;
      }
    }
  }
  
  return maxWater;
}

Раннее прерывание поиска

function maxArea(heights) {
  // Находим максимальную высоту для оценки верхней границы
  const maxHeight = Math.max(...heights);
  let maxWater = 0;
  let left = 0;
  let right = heights.length - 1;
  
  while (left < right) {
    const width = right - left;
    const height = Math.min(heights[left], heights[right]);
    maxWater = Math.max(maxWater, width * height);
    
    // Если максимально возможная площадь меньше текущей максимальной,
    // нет смысла продолжать поиск
    const maxPossibleArea = maxHeight * (right - left - 1);
    if (maxPossibleArea <= maxWater) {
      break;
    }
    
    if (heights[left] < heights[right]) {
      left++;
    } else {
      right--;
    }
  }
  
  return maxWater;
}

Заключение

При решении задачи "Контейнер с водой" важно помнить:

• 🤹‍♂️ Метод двух указателей - элегантное и эффективное решение с линейной сложностью
• 📊 Ключевая интуиция: всегда двигаем указатель, указывающий на меньшую высоту
• 🧠 Понимание геометрической интерпретации задачи помогает найти оптимальное решение

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