Контейнер с водой
Дан целочисленный массив 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
На каждом шаге следует двигать указатель, указывающий на меньшую высоту, так как это единственный способ потенциально увеличить площадь контейнера.