Ваша задача — выбрать две вертикальные линии на плоскости, чтобы вместе с осью X они образовали контейнер, в который поместится максимум воды. Даны высоты этих линий в массиве.
Как действовать:
1. Ставим два указателя: один — на начало, второй — на конец массива.
2. Считаем объем текущего контейнера: ширина между указателями умножается на минимальную из двух высот.
3. Двигаем указатель с меньшей высотой внутрь. Если обе высоты равны — можно сдвигать любой.
4. Запоминаем максимум, повторяем шаги, пока указатели не встретятся.
По сути, это жадный алгоритм с двумя указателями, который перебирает края и минимизирует лишние проверки.
Пример реализации:
public int MaxArea(int[] h)
{
int l = 0, r = h.Length - 1, m = 0;
while (l < r)
{
m = Math.Max(m, (r - l) * Math.Min(h[l], h[r]));
if (h[l] < h[r]) l++; else r--;
}
return m;
}
➡️ Попробовать на литкоде
🐸 Библиотека шарписта
#dotnet_challenge