DEV Community

Ivan
Ivan

Posted on

16 14 5 4 7

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

Давайте разберем задачу контейнера с наибольшим количеством воды. Ее можно найти по ссылке 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
Enter fullscreen mode Exit fullscreen mode

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

var left: Int = 0
var right: Int = height.size - 1
Enter fullscreen mode Exit fullscreen mode

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

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

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

...
max = Math.max(curr, max)
...
Enter fullscreen mode Exit fullscreen mode

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

...
if (height[left] < height[right]) {
    left++
} else {
    right--
}
...
Enter fullscreen mode Exit fullscreen mode

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

...
return max
Enter fullscreen mode Exit fullscreen mode

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

  • По времени - 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
}
Enter fullscreen mode Exit fullscreen mode

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

Top comments (5)

Collapse
 
nananana10n profile image
Nanah

❤🦄

Collapse
 
irchiiik profile image
Ирина Лютина

🧐👍

Collapse
 
a_alzouby profile image
Ahmad J Alzouby

❤🦄

Collapse
 
kukshinov profile image
Kirill
Comment hidden by post author
Collapse
 
sergey3205799 profile image
Sergey3205799
Comment hidden by post author

Some comments have been hidden by the post's author - find out more

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

👋 Kindness is contagious

Dive into an ocean of knowledge with this thought-provoking post, revered deeply within the supportive DEV Community. Developers of all levels are welcome to join and enhance our collective intelligence.

Saying a simple "thank you" can brighten someone's day. Share your gratitude in the comments below!

On DEV, sharing ideas eases our path and fortifies our community connections. Found this helpful? Sending a quick thanks to the author can be profoundly valued.

Okay