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


Вам дан целочисленный массив height длины n. Проведено n вертикальных линий так, что две конечные точки первой линии — (i, 0) и (i, height[i]).

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

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

Обратите внимание, что наклонять контейнер нельзя.

Постановка задачи взята с сайта: https://leetcode.com/problems/container-with-most-water/


Подход грубой силы

var maxArea = function (heights) {
    let maxArea = 0;
    for (let p1 = 0; p1 < heights.length; p1++) {
        for (let p2 = p1 + 1; p2 < heights.length; p2++) {
            const length = Math.min(heights[p1], heights[p2]);
            const width = p2 - p1;
            const area = length * width;
            maxArea = Math.max(area, maxArea);
        }
    }
    return maxArea;
}
Войдите в полноэкранный режим Выйти из полноэкранного режима

Сложность по времени : O(n^2)
Сложность пространства : O(1)

Оптимизированный подход

    let maxArea = 0, p1 = 0, p2 = heights.length - 1;
    while (p1 < p2) {
        const height = Math.min(heights[p1], heights[p2]);
        const width = p2 - p1;
        const area = height * width;
        maxArea = Math.max(maxArea, area);
        if (heights[p1] <= heights[p2]) {
            p1++;
        } else {
            p2--;
        }
    }
    return maxArea;
Войти в полноэкранный режим Выход из полноэкранного режима

Временная сложность : O(n)
Сложность пространства : O(1)

Оцените статью
Procodings.ru
Добавить комментарий