Описание испытания

Вам дан массив целых чисел 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

Интуиция

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

Объяснение:

  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), на основе сравнения высот в их соответствующих позициях.

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

  1. 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;
}