[Условие]. Leetcode 11. Container With Most Water

Ссылка на задачу на Leetcode
Решение

У нас есть несколько вертикальных линий, расположенных последовательно через равное расстояние. На вход получаем массив, в котором содержатся их высоты.
Задача - найти максимальную площадь прямоугольника, сторонами которого являются две из этих линий.

Кейс 1
height = [1,8,6,2,5,4,8,3,7] (на картинке)
Ответ: 49 (между линиями с высотой 8 и 7)

#medium #arrays #twopointers

@leetcode_furrycat

[Решение]. Leetcode 11. Container With Most Water

Условие задачи

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

function getVolume(height: number[], left: number, right: number): number {
    const h1 = height[left]
    const h2 = height[right]
    return Math.min(h1, h2) * (right - left)
}

function maxArea(height: number[]): number {
    let left = 0
    let right = height.length - 1
    let max = 0

    while(left < right) {
        max = Math.max(max, getVolume(height, left, right))

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

    return max
}

#medium #arrays #twopointers

@leetcode_furrycat