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

Иногда достаточно простые задачи маскируют нестандартными формулировками. Так и в этой задаче сперва формулировки могут вас сбить с толку. На самом деле ничего сложного, нужно просто найти прямоугольник с наибольшей площадью. Высоты прямоугольников задаются входным масивом. Ширина — разность индексов во входящем массиве между выбранными высотами.

Сложность: 🟠 Cредняя

ℹ️ Описание

Вам дан целочисленный массив высот height длиною n.

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


⚠️ Ограничения

🔹В массиве всегда есть минимум 2 элемента, но не больше 10 ^ 5
🔹В качестве значений могут быть числа в диапазоне от 0 до 10 ^ 4


1️⃣ Пример

Входящие данные: [1,8,6,2,5,4,8,3,7]
Ответ: 49

Прямоугольник с наибольшой площадью образуют второй и девятый (последний) элемент массива. В этом случае высота прямоугольника — 7 (минимальная высота из двух вариантов — 8 и 7). Длина прямоугольника (разность индексов этих высот) также равна 7.

2️⃣ Пример

Входящие данные: [1,1]
Ответ: 1

В данном случае возможно получить только один прямоугольник площадью 1.


✅ Решение

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

Но, есть и более оптимальный подход — «скользящее окно». Для этого нам понадобятся 2 указателя на границы окна (в нашем случае просто индексы высот). Задача будет сводиться к тому, чтобы правильно сдвигать границы окна.

🔘 В качестве изначальных границ возьмем весь массив (т.е. левая граница стоит на нулевом индексе, а правая на последнем).

🔘 Вычислим размер получившегося прямоугольника.

🔘 «Сузим окно» — для этого выберем какую границу сдвигать. При уменьшении длины получить большую площадь мы можем только увеличив высоту:
⏺ если левая высота меньше чем правая, сдвигаем левый указатель на единицу вправо;
⏺ если правая высота меньше чем левая, сдвигаем правый указатель на единицу влево.

🔘 Вычисляем размер прямоугольника, образованного новым «окном» и запоминаем больший из двух.

🔘 Продолжаем «сужать окно», пока правый и левый указатели не сойдутся.

Посмотреть реализацию в блоге

🅾️ Оценка сложности

По времени

На каждой итерации мы двигаем либо правую, либо левую границу окна. Таким образом, суммарно мы подвинем границу O(n - 1) раз. Это единственная переменная величина. Таким образом, алгоритм имеет линейный порядок роста O(n).

По памяти

Мы никак не преобразуем входящие данные и не храним промежуточные результаты (как в случае с брутфорсом). Сложность по памяти константная — O(1).