sc/Все задачи

Контейнер с водой

СредняяДва указателяcontainer-with-most-water

Дан целочисленный массив heights, где heights[i] представляет высоту i-го столбца.

Вы можете выбрать любые два столбца для формирования контейнера. Верните максимальное количество воды, которое может вместить контейнер.

Пример 1:

Input: heights = [1,8,6,2,5,4,8,3,7]
Output: 49
Объяснение: В данном случае максимальная площадь воды (49) будет между столбцами с высотами 8 и 7

Пример 2:

Input: heights = [1,1]
Output: 1

Рекомендуемая временная и пространственная сложность

Оптимальное решение должно иметь временную сложность O(n) и пространственную сложность O(1), где n — длина массива.

Подсказка 1

Площадь контейнера определяется двумя факторами: шириной (расстояние между столбцами) и высотой (минимальная высота из двух выбранных столбцов).

Подсказка 2

Вместо перебора всех возможных пар столбцов (что даёт O(n²)), подумайте об использовании двух указателей, начинающих с противоположных концов массива.

Подсказка 3

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

JavaScript Решения:

class Solution {
    // Решение с двумя указателями
    maxArea(heights) {
        let maxWater = 0;
        let left = 0;
        let right = heights.length - 1;
        
        while (left < right) {
            const width = right - left;
            const height = Math.min(heights[left], heights[right]);
            const area = width * height;
            maxWater = Math.max(maxWater, area);
            
            if (heights[left] < heights[right]) {
                left++;
            } else {
                right--;
            }
        }
        
        return maxWater;
    }
    // Время: O(n), Память: O(1)

    // Решение перебором (не оптимальное)
    maxAreaBruteForce(heights) {
        let maxWater = 0;
        for (let i = 0; i < heights.length; i++) {
            for (let j = i + 1; j < heights.length; j++) {
                const width = j - i;
                const height = Math.min(heights[i], heights[j]);
                maxWater = Math.max(maxWater, width * height);
            }
        }
        return maxWater;
    }
    // Время: O(n²), Память: O(1)
}

Java Решения:

class Solution {
    // Решение с двумя указателями
    public int maxArea(int[] heights) {
        int maxWater = 0;
        int left = 0;
        int right = heights.length - 1;
        
        while (left < right) {
            int width = right - left;
            int height = Math.min(heights[left], heights[right]);
            int area = width * height;
            maxWater = Math.max(maxWater, area);
            
            if (heights[left] < heights[right]) {
                left++;
            } else {
                right--;
            }
        }
        
        return maxWater;
    }
    // Время: O(n), Память: O(1)

    // Решение перебором (не оптимальное)
    public int maxAreaBruteForce(int[] heights) {
        int maxWater = 0;
        for (int i = 0; i < heights.length; i++) {
            for (int j = i + 1; j < heights.length; j++) {
                int width = j - i;
                int height = Math.min(heights[i], heights[j]);
                maxWater = Math.max(maxWater, width * height);
            }
        }
        return maxWater;
    }
    // Время: O(n²), Память: O(1)
}

Python Решения:

class Solution:
    # Решение с двумя указателями
    def maxArea(self, heights: List[int]) -> int:
        max_water = 0
        left = 0
        right = len(heights) - 1
        
        while left < right:
            width = right - left
            height = min(heights[left], heights[right])
            area = width * height
            max_water = max(max_water, area)
            
            if heights[left] < heights[right]:
                left += 1
            else:
                right -= 1
                
        return max_water
    # Время: O(n), Память: O(1)

    # Решение перебором (не оптимальное)
    def maxAreaBruteForce(self, heights: List[int]) -> int:
        max_water = 0
        for i in range(len(heights)):
            for j in range(i + 1, len(heights)):
                width = j - i
                height = min(heights[i], heights[j])
                max_water = max(max_water, width * height)
        return max_water
    # Время: O(n²), Память: O(1)

Для каждого языка представлены два решения:

Оптимальное решение с использованием техники двух указателей - O(n)
Решение перебором (брутфорс) - O(n²)

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

solution.js · сохранено

Входные данные

[1,8,6,2,5,4,8,3,7]

Ожидаемый результат