Container With Most Water

Q: Какова временная сложность задачи «Контейнер с наибольшим количеством воды»?

Решение с двумя указателями работает за время O(n) и использует O(1) дополнительной памяти. На каждом шаге один указатель перемещается на одну позицию внутрь, поэтому выполняется не более n-1 шагов. Проверка каждой пары занимает O(n²), а сортировка линий по высоте — O(n log n).

Q: Зачем перемещать указатель к более короткой линии?

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

Q: Является ли задача «Контейнер с наибольшим количеством воды» жадной задачей?

Да. На каждом шаге делается локальный выбор, который уже не отменяется: отбрасывается более короткая линия. Этот выбор безопасен, потому что любой контейнер, который исключает этот шаг, не лучше уже измеренного. Поэтому задача относится и к жадным алгоритмам, и к методу двух указателей.

Q: Чем задача Container With Most Water отличается от задачи Trapping Rain Water?

Здесь важны только две выбранные линии, а линии между ними игнорируются, поэтому ответ — один прямоугольник. В задаче Trapping Rain Water каждый столбик сплошной, и вода скапливается над каждым столбиком на высоту до уровня более низкого из самых высоких столбиков по обе стороны от него, поэтому ответ — сумма по всем позициям. Для обеих задач существуют решения за O(n) с двумя указателями, но правила перемещения указателей и то, что нужно складывать, различаются.

СреднеДва указателя Жадные алгоритмы

+10

Дан список height неотрицательных целых чисел. Линия i — это вертикальная стенка высотой height[i], расположенная в позиции i. Любые две линии вместе с землёй образуют контейнер, который вмещает столько воды, сколько составляет высота более короткой линии, умноженная на расстояние между двумя линиями. Остальные линии не мешают. Верните максимальный объём воды, который может вместить одна пара линий.

Функция

maxArea(height: integer-array) → integer

heightinteger-array: высоты строк в позициях 0, 1, 2 и так далее
Возвращаетinteger: наибольшее количество воды, которое могут вместить две линии

Ограничения

2 ≤ height.length ≤ 10⁴
0 ≤ height[i] ≤ 10⁴
Ответ не превышает 10⁸, поэтому он помещается в 32-битное целое число.

Примеры

Ввод: height = [3, 7, 2, 5, 4, 7, 3, 6]
Вывод: 36
Пояснение: Линии в позициях 1 и 7 имеют высоту 7 и 6 и находятся на расстоянии 6 друг от друга, поэтому они вмещают 6 × 6 = 36. Две самые высокие линии — высотой 7 в позициях 1 и 5 — вмещают только 7 × 4 = 28, а крайняя пара вмещает 3 × 7 = 21.

+15 скрытых тестов при отправке

Дополнительный вопрос

Здесь строки между двумя выбранными тобой игнорируются. Если бы каждая строка была сплошной полосой, сколько воды собралось бы между ними всеми? Можешь ли ты вычислить это также за O(n)?

Решение

Есть примерно n²/2 пар линий, поэтому для 10^4 линий проверка всех пар означает 5 × 10^7 вычислений произведения. Выход в том, что объём воды зависит только от более короткой линии в паре: как только вы выяснили, что линия является более короткой стороной самого широкого контейнера, который она ещё может образовать, никакой более узкий контейнер с её участием не даст лучшего результата. Два указателя позволяют использовать этот факт и выполнить один проход с обоих концов.

Проверьте каждую пару

Верно, но не успевает на самых больших тестах

Идея

Каждый контейнер — это пара позиций i < j. Вода поднимается, пока не перельётся через более короткую стенку, а дно между стенками имеет ширину j - i, поэтому вместимость пары равна min(height[i], height[j]) × (j - i). Проверьте каждую пару, оставьте наибольшую вместимость — и по определению получите ответ.

Проблема в количестве пар. Для n линий их n(n-1)/2: около 5 × 10^7 для 10^4 линий, а при каждом удвоении списка их становится в четыре раза больше. Компилируемый язык справится с этим за долю секунды, но Python, Ruby или R потребуется много секунд, а при n = 10^5 число пар растёт слишком быстро для любого языка.

Алгоритм

Установи best равным 0.
Для каждого i и каждого j после него вычисли min(height[i], height[j]) × (j - i).
Сохрани большее из значений best и этого значения.
Верни best.

def maxArea(height):
    n = len(height)
    best = 0
    for i in range(n):
        for j in range(i + 1, n):
            water = min(height[i], height[j]) * (j - i)
            best = max(best, water)
    return best

Сначала самые высокие строки

Идея

Посмотри на контейнер со стороны его более короткой линии. Если линия i — более короткая сторона, то объём воды равен height[i], умноженной на расстояние, а в пару ей можно взять любую линию не ниже неё. Значит, лучший контейнер, в котором i — более короткая сторона, образуется с самой дальней линией, которая не ниже неё.

Чтобы быстро находить такие линии, расположи линии от самой высокой к самой низкой. Когда очередь доходит до линии i, каждая линия, расположенная перед ней, не ниже неё, а самая дальняя из них находится либо на самом левом, либо на самом правом из уже расположенных индексов. Отслеживай эти два индекса — lo и hi, — и линия i в лучшем случае вмещает height[i] × max(i - lo, hi - i). Ответ — наибольшее из этих значений, поскольку лучший контейнер учитывается, когда очередь доходит до его более короткой линии.

В первом примере две линии высотой 7 на позициях 1 и 5 идут первыми и вмещают 28. Следующей идёт линия высотой 6 на позиции 7, где lo = 1 и hi = 5; она вмещает 6 × 6 = 36. Ни одна более низкая линия не даст большего результата. Равные по высоте линии могут идти в любом порядке: та из двух равных линий, которая идёт второй, увидит первую в качестве партнёра.

Сортировка требует O(n log n), а проход — O(n), что достаточно быстро. При этом для хранения порядка всё ещё нужна память O(n), а следующий подход избавляется и от сортировки, и от этой памяти.

Алгоритм

Отсортируй индексы по высоте, от самого высокого к самому низкому.
Установи lo и hi равными первому индексу в этом порядке, а best — равным 0.
Для каждого следующего индекса i вычисли произведение height[i] на большее из значений i - lo и hi - i и сохрани лучшее значение.
Обнови lo и hi, включив в диапазон i.
Верни best.

def maxArea(height):
    # Indices from the tallest line to the shortest.
    order = sorted(range(len(height)), key=lambda i: height[i], reverse=True)
    lo = hi = order[0]  # leftmost and rightmost index among the lines placed so far
    best = 0
    for i in order[1:]:
        # Every placed line is at least as tall as line i, so line i is the
        # shorter side, and its best partner is the placed line farthest away.
        best = max(best, height[i] * max(i - lo, hi - i))
        lo = min(lo, i)
        hi = max(hi, i)
    return best

Два указателя с обоих концов

Идея

Начни с самого широкого контейнера: left = 0 и right = n-1 — и измерь его. Теперь можно убрать одну из двух линий, и выбор очевиден: убери более короткую. Допустим, height[left] ≤ height[right]. Любой другой контейнер с линией left будет образован парой с линией, расположенной ближе, чем right, поэтому он будет уже, а его высота по-прежнему будет не больше height[left]. Ни один из таких контейнеров не вместит больше воды, чем измеренный, поэтому линия left больше не нужна, и left сдвигается на один шаг вправо. Если вместо этого сдвинуть более высокую линию, ограничение на высоту останется прежним, а ширина уменьшится — результат может быть только хуже. Если высоты равны, обе линии больше не нужны, и можно сдвинуть любую из них.

На каждом шаге одна линия исключается окончательно, поэтому после n-1 шагов указатели встретятся. Лучшую пару мы не пропустим: когда одну из двух её линий убирают впервые, измеренный в этот момент контейнер вмещает как минимум столько же воды.

Для массива [3, 7, 2, 5, 4, 7, 3, 6] позиции 0 и 7 вмещают 3 × 7 = 21. Линия высотой 3 короче, поэтому left сдвигается на позицию 1. Позиции 1 и 7 вмещают 6 × 6 = 36, и теперь линия высотой 6 короче, поэтому right сдвигается на позицию 6. Следующие контейнеры вмещают 15, 28, 12, 10 и 2, поэтому ответ остаётся равен 36.

Алгоритм

Задайте left = 0, right = n-1 и best = 0.
Пока left < right, вычисляйте min(height[left], height[right]) × (right - left) и сохраняйте наилучшее значение.
Если height[left] < height[right], передвиньте left на один шаг вправо. Иначе передвиньте right на один шаг влево.
Когда указатели встретятся, верните best.

def maxArea(height):
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        water = min(height[left], height[right]) * (right - left)
        best = max(best, water)
        # The shorter line cannot do better with any line closer in, so drop it.
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return best

Ловушки и крайние случаи

Цикл с двумя указателями короткий, поэтому ошибки кроются в деталях.

Перемещение более высокой линии. В первом примере результат равен 21 вместо 36: линия высотой 6 на позиции 7 — более высокая в первой паре, поэтому она уходит, так и не встретившись с линией высотой 7 на позиции 1.
Использование более высокой линии или среднего значения двух линий в качестве высоты. Вода переливается через более низкую стенку, поэтому высота равна минимуму.
Ошибка на единицу при вычислении ширины. Линии на позициях i и j находятся на расстоянии j - i, а не j - i + 1, поэтому две соседние линии вмещают объём, равный их меньшей высоте, умноженной на 1.
Предположение, что ответ задаётся самой высокой линией или внешней парой. В первом примере две линии высотой 7 вмещают 28, а внешняя пара — 21, тогда как ответ равен 36.
Переполнение при больших ограничениях. Здесь объём воды остаётся меньше 10^8, но при высотах и длинах, близких к 10^5, произведение превышает 2^31, поэтому требуется 64-битное целое число.

Частые вопросы4

Какова временная сложность задачи «Контейнер с наибольшим количеством воды»?

Решение с двумя указателями работает за время O(n) и использует O(1) дополнительной памяти. На каждом шаге один указатель перемещается на одну позицию внутрь, поэтому выполняется не более n-1 шагов. Проверка каждой пары занимает O(n²), а сортировка линий по высоте — O(n log n).

Зачем перемещать указатель к более короткой линии?

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

Является ли задача «Контейнер с наибольшим количеством воды» жадной задачей?

Да. На каждом шаге делается локальный выбор, который уже не отменяется: отбрасывается более короткая линия. Этот выбор безопасен, потому что любой контейнер, который исключает этот шаг, не лучше уже измеренного. Поэтому задача относится и к жадным алгоритмам, и к методу двух указателей.

Чем задача Container With Most Water отличается от задачи Trapping Rain Water?

Здесь важны только две выбранные линии, а линии между ними игнорируются, поэтому ответ — один прямоугольник. В задаче Trapping Rain Water каждый столбик сплошной, и вода скапливается над каждым столбиком на высоту до уровня более низкого из самых высоких столбиков по обе стороны от него, поэтому ответ — сумма по всем позициям. Для обеих задач существуют решения за O(n) с двумя указателями, но правила перемещения указателей и то, что нужно складывать, различаются.

Python

def maxArea(height):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Ввод

height = [3, 7, 2, 5, 4, 7, 3, 6]

Ожидается

Container With Most Water

Функция

Ограничения

Примеры

Подсказки

Решение

Проверьте каждую пару

Сначала самые высокие строки

Два указателя с обоих концов

Ловушки и крайние случаи

Частые вопросы4

Похожие задачи