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

#kotlin #algorithms #leetcode #medium

Давайте разберем задачу контейнера с наибольшим количеством воды. Ее можно найти по ссылке Container With Most Water

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

Дан целочисленный массив значений высоты height размера n, т.е. нарисовано n вертикальных линий.

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

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

Примеры входных данных

Пример 1

Входные данные:
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Результат:
49

Пример 2

Входные данные:
height = [1, 1]
Результат:
1

Решение

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

Решение по шагам

1) Сначала надо инициализировать переменную max, которую вернем в качестве результата.

var max: Int = 0

2) Затем необходимо инициализировать левый и правый указатель.

var left: Int = 0
var right: Int = height.size - 1

3) Для итерации по списку вершин реализуем цикл while. Условием окончания цикла является равенство вершин left и right, либо то что вершина right оказалась левее вершины left. На каждом этапе считаем текущий объем воды.

while (left < right) {
    val curr = Math.min(height[left], height[right]) * (right - left)
    ...
}

4) Далее сравниваем текущий объем воды с максимальным и наибольшее значение присваиваем переменной результата.

...
max = Math.max(curr, max)
...

5) Затем сравниваем левое и правое значение высоты вершин. Если правая вершина больше, то необходимо перевинуть левую вершину к центру. Иначе - двигаем правую вершину к центру.

...
if (height[left] < height[right]) {
    left++
} else {
    right--
}
...

6) В конце возвращаем переменную max в качестве результата.

...
return max

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

По времени - O(n). По списку выполняется один проход.
По памяти - O(1). Количество используемой памяти не зависит от размера входного массива.

Полное решение

fun maxArea(height: IntArray): Int {
    var max: Int = 0
    var left: Int = 0
    var right: Int = height.size - 1
    while (left < right) {
        val curr = Math.min(height[left], height[right]) * (right - left)
        max = Math.max(curr, max)
        if (height[left] < height[right]) {
            left++
        } else {
            right--
        }
    }
    return max
}