Описание испытания
Вам дан массив целых чисел height
длины n
. Нарисовано n
вертикальных линий, так что двумя конечными точками ith
линии являются (i, 0)
и (i, height[i])
.
Найдите две линии, которые вместе с осью абсцисс образуют контейнер, содержащий наибольшее количество воды.
Возвращает максимальное количество воды, которое может храниться в контейнере.
Обратите внимание, что вы не можете наклонять контейнер.
Пример 1
Input: height = [1,8,6,2,5,4,8,3,7] Output: 49 Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Пример 2
Input: height = [1,1] Output: 1
Интуиция
Метод двух указателей начинается с самого широкого контейнера и перемещает указатели внутрь на основе сравнения высот.
Увеличение ширины контейнера может привести к увеличению области только в том случае, если высота новой границы больше. Перемещая указатели к центру, мы исследуем контейнеры с потенциалом для больших площадей.
Объяснение:
- Инициализируйте переменные:
left
для представления левого указателя, начиная с начала контейнера (индекс 0).right
для представления правого указателя, начиная с конца контейнера (индексheight.size() - 1
).maxArea
для отслеживания максимальной найденной области, изначально установленной на 0.
2. Входим в цикл, используя условие left < right
, означающее, что указатели еще не пересеклись.
3. Рассчитать текущую площадь:
- Используйте функцию
min
, чтобы найти минимальную высоту между указателямиleft
иright
. - Умножьте минимальную высоту на ширину, которая является разницей между индексами указателей:
(right - left)
. - Сохраните это значение в переменной
currentArea
.
4. Обновите максимальную площадь:
- Используйте функцию
max
, чтобы сравнитьcurrentArea
сmaxArea
. - Если
currentArea
большеmaxArea
, обновитеmaxArea
наcurrentArea
.
5. Переместите указатели внутрь: (подробно объяснено ниже)
- Проверьте, меньше ли высота указателя
left
, чем высота указателяright
. - Если это так, увеличьте указатель
left
, переместив его к центру контейнера. - В противном случае уменьшите указатель
right
, также переместив его к центру.
6. Повторяйте шаги с 3 по 5, пока указатели не встретятся (left >= right
), что означает, что все возможные контейнеры были исследованы.
7. Возвратите maxArea
, представляющее максимальную площадь среди всех контейнеров.
Обновите максимальную площадь:
Цель этого условия состоит в том, чтобы определить, какой указатель двигаться внутрь, левый указатель (i
) или правый указатель (j
), на основе сравнения высот в их соответствующих позициях.
Представьте, что у вас есть два контейнера, представленные высотами левого и правого указателей. Условие проверяет, какой контейнер имеет меньшую высоту, и перемещает указатель, соответствующий этому контейнеру.
- If
height[i] > height[j]
:
- Это означает, что высота левого контейнера больше высоты правого контейнера.
- Перемещение правого указателя (
j
) не увеличит потенциальную площадь, поскольку ограничивающим фактором является высота правого контейнера. - Итак, чтобы исследовать контейнеры с возможностью увеличения площади, нам нужно переместить правый указатель внутрь, уменьшив
j
.
2. If height[i] <= height[j]
:
- Это означает, что высота левого контейнера меньше или равна высоте правого контейнера.
- Перемещение левого указателя (
i
) не увеличит потенциальную площадь, поскольку ограничивающим фактором является высота левого контейнера. - Итак, чтобы исследовать контейнеры с возможностью увеличения площади, нам нужно переместить левый указатель внутрь, увеличив
i
.
Выполняя эти движения указателя, мы гарантируем, что всегда исследуем контейнеры с потенциалом для больших областей. Подход основан на наблюдении, что увеличение ширины контейнера может привести к увеличению площади только в том случае, если высота новой границы больше.
Следуя этому условию и соответствующим образом перемещая указатели, алгоритм исследует все возможные контейнеры и находит тот, у которого максимальная площадь.
function maxArea(height: number[]): number { let left = 0; let right = height.length - 1; let maxArea = 0; while (left < right) { const currentArea = Math.min(height[left], height[right]) * (right - left); maxArea = Math.max(maxArea, currentArea); if (height[left] < height[right]) { left++; } else { right--; } } return maxArea; }